內(nèi)容
給出一個字符串數(shù)組words組成的一本英語詞典。從中找出最長的一個單詞乳讥，該單詞是由words詞典中其他單詞逐步添加一個字母組成聪舒。若其中有多個可行的答案，則返回答案中字典序最小的單詞。
若無答案蝠筑，則返回空字符串狞膘。
示例 1:
輸入:
words = ["w","wo","wor","worl", "world"]
輸出: "world"
解釋:
單詞"world"可由"w", "wo", "wor", 和 "worl"添加一個字母組成。
示例 2:
輸入:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
輸出: "apple"
解釋:
"apply"和"apple"都能由詞典中的單詞組成什乙。但是"apple"得字典序小于"apply"挽封。
注意:
所有輸入的字符串都只包含小寫字母。
words數(shù)組長度范圍為[1,1000]臣镣。
words[i]的長度范圍為[1,30]场仲。
思路
既然是找最長的單詞，然后又是一個無序數(shù)組退疫，那么首先排序渠缕。
然后觀察，如果這個最長的單詞是有效的褒繁，那么它的依次從右側減去一個字母的組合都應該在數(shù)組中存在亦鳞，這個時候考慮到，如果每次都去這么大的數(shù)組中遍歷棒坏，那么肯定超級慢燕差。所以直接將數(shù)組中的所有字符串放入一個對象map中，每次需要判斷單詞的部分子串是否存在時坝冕，就去map中找徒探。
然后還有個問題就是，這種單詞可能有多個喂窟，這里需要將他們進行一個字符串大小的比較测暗，通過改寫一下sort方法即可。
代碼
/**
詞典中最長的單詞
既然是找最長的單詞磨澡，然后又是一個無序數(shù)組碗啄，那么首先排序。
然后觀察稳摄，如果這個最長的單詞是有效的稚字，那么它的依次從右側減去一個字母的組合都應該在數(shù)組中存在，這個時候考慮到厦酬，如果每次都去這么大的數(shù)組中遍歷胆描，那么肯定超級慢。所以直接將數(shù)組中的所有字符串放入一個對象map中仗阅，每次需要判斷單詞的部分子串是否存在時昌讲，就去map中找。
然后還有個問題就是霹菊，這種單詞可能有多個剧蚣，這里需要將他們進行一個字符串大小的比較支竹，通過改寫一下sort方法即可。
* @param {string[]} words
* @return {string}
*/
var longestWord = function (words) {
var map = {};
words.sort(function (a, b) {
return a.length - b.length
})
for (var i = 0; i < words.length; i++) {
map[words[i]] = 1;
}
var maxlens = [];
for (var i = words.length - 1; i >= 0; i--) {
var now = words[i] || '';
var next = words[i - 1] || '';
maxlens.push(now);
if (now.length > next.length) {
for (var j = 0; j < maxlens.length; j++) {
if (!check(maxlens[j])) {
maxlens.splice(j, 1);
j--;
}
}
if (maxlens.length > 0) {
maxlens.sort(function (a, b) {
return a > b ? 1 : -1;
})
return maxlens[0];
}
}
}
function check(str) {
for (var i = 0; i < str.length - 1; i++) {
if (map[str.slice(0, str.length - i - 1)] != 1) {
return false;
}
}
return true;
}
return -1;
};
