0720. Longest Word in Dictionary

# 720. Longest Word in Dictionary#

## 题目 #

Given a list of strings `words` representing an English Dictionary, find 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".
``````

Example 2:

``````Input:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation:
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
``````

Note:

• All the strings in the input will only contain lowercase letters.
• The length of `words` will be in the range `[1, 1000]`.
• The length of `words[i]` will be in the range `[1, 30]`.

## 解题思路 #

• 给出一个字符串数组，要求找到长度最长的，并且可以由字符串数组里面其他字符串拼接一个字符组成的字符串。如果存在多个这样的最长的字符串，则输出字典序较小的那个字符串，如果找不到这样的字符串，输出空字符串。
• 这道题解题思路是先排序，排序完成以后就是字典序从小到大了。之后再用 map 辅助记录即可。

## 代码 #

``````
package leetcode

import (
"sort"
)

func longestWord(words []string) string {
sort.Strings(words)
mp := make(map[string]bool)
var res string
for _, word := range words {
size := len(word)
if size == 1 || mp[word[:size-1]] {
if size > len(res) {
res = word
}
mp[word] = true
}
}
return res
}

``````

Sep 6, 2020