Given an array of strings words
representing an English Dictionary, return the longest word in words
that can be built one character at a time by other words in words
.
If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.
Example 1:
Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
I knew that the best solution is “Tire”. But, I used Hash first and that is method of brute force. I will used “Tire” later.
Sort first. check the word with hashset one by one. If those words are include in hashset, I will compare length of result and the word, and replace result to longer word.
我知道這題的最佳解是用Tire,先使用Hash的方式解這題,之後會再用Tire解一次,先來說明暴力解的方式。
暴力解:
先做排序,逐一檢查每個字的前面字串是否有存在hash裡面。如果沒有,就表示這個字串並不符合。如果有,則檢查是否為最長的字。