LeetCode Contest 57
这次比赛考细节/模拟。
第一题Longest Word in Dictionary
我是用trie做的。首先将单词按照长度排序,然后将单词一一放进一个trie中。用trie是因为将单词放入trie中的同时也可以判断单词的前面部分是否在trie里(这也是按长度排序的原因)。
class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
words.sort(key=lambda x: len(x))
tree = {'#': {}}
ans = ''
for word in words:
p = tree
ok = True
for c in word:
if c not in p:
p[c] = {}
ok = ok and '#' in p
p = p[c]
p['#'] = {}
if ok and (len(word) > len(ans) or word < ans):
ans = word
return ans