Python 字典中最长的单词
pythonserver side programmingprogramming更新于 2023/11/9 23:49:00
假设我们有一个表示英语字典的单词列表，我们必须在给定的单词列表中找到最长的单词，该单词可以由单词中的其他单词一次一个字符地构建。如果有多个可能的答案，则返回具有最小字典顺序的最长单词。如果没有答案，则返回空字符串。
因此，如果输入为 ["h","he","hel","hell","hello"]，则输出将为 "hello"
为了解决这个问题，我们将遵循以下步骤 −
- trie := a new map
- 定义一个函数 insert()。这将获取单词
- now := trie
- 对于单词中的每个 c，执行
- 如果 c 不在 now −
- now[c] = {'#', False}，则
- now := now[c]
- now['#'] := True
- 如果 c 不在 now −
- 定义一个函数 search() 。这将获取单词
- now := trie
- 对于单词中的每个 c，执行
- 如果 '#'在 now 中且 not now['#'] 为 True，则
- 返回 False
- now := now[c]
- 返回 now['#']
- 如果 '#'在 now 中且 not now['#'] 为 True，则
- 对于 words 中的每个单词，执行
- 调用 insert(word)
- ans := 空字符串
- 对于 words 中的每个单词，执行
- 如果 search(word) 和(word 的大小 > ans 的大小或 (word 的大小与 ans 的大小相同且 word < ans))，则
- ans := word
- 如果 search(word) 和(word 的大小 > ans 的大小或 (word 的大小与 ans 的大小相同且 word < ans))，则
- 返回 ans
让我们看看下面的实现以便更好地理解 −
示例
class Solution:
def longestWord(self, words):
self.trie = {}
def insert(word):
now = self.trie
for c in word:
if c not in now: now[c] = {'#': False}
now = now[c]
now['#'] = True
def search(word):
now = self.trie
for c in word:
if '#' in now and not now['#']: return False
now = now[c]
return now['#']
for word in words:
insert(word)
ans = ""
for word in words:
if (search(word) and (len(word) > len(ans) or (len(word) == len(ans) and word < ans))):
ans = word
return ans
ob = Solution()
print(ob.longestWord(["h","he","hel","hell", "hello"]))
输入
["h","he","hel","hell", "hello"]
输出
hello
