题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个词典，规定合法的单词是存在另一个单词右侧加一个字母所得（单字母直接合法），求合法单词中长度最长且字典序最小的。

思路分享

  • 本题有个没有明说的要求，是要必须从单字母开始，如果有一个 rm，还是没有 r，那么 rm 后面衍生的都不合法。

  • 老样子，通过哈希表和切片可以实现快速查找一个单词的前缀是否存在。此外，通过字典树则能直接往后筛选，参考题解是一边建树一边筛选记录，实际上也可以先把字典树建好，然后用单字母路线向下遍历，需要整条路线都是末节点才算是合法答案（即都是一个个字母加起来的）

    https://leetcode.cn/problems/longest-word-in-dictionary/solutions/1342188/ci-dian-zhong-zui-chang-de-dan-ci-by-lee-k5gj/

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def longestWord(self, words: List[str]) -> str:
        root = {}
        words.sort(key=lambda x : len(x))
        # print(words)
        ans = ""
        for i, s in enumerate(words):
            cur = root
            l = len(s)
            if l == 1 and s not in cur:
                cur[s] = {}
                cur[s]["#"] = {}
                if len(s) > len(ans) or ans > s:
                    ans = s
                continue

            increase = False
            for j, c in enumerate(s):
                if c not in cur:
                    cur[c] = {}
                
                cur = cur[c]
                if j == l-2 and "#" in cur:
                    increase = True
                    if len(s) > len(ans) or ans > s:
                        ans = s

            if increase:
                cur["#"] = {}
        return ans