题目浅析

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

  • 简单地说，就是给一个词典，这个词典是一系列词根（前缀），现在给一个字符串，请把其中所有的可由词典词根衍生的单词还原为词根。

思路分享

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

  • 参考题解
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
31
32
33
34
class Node:
    def __init__(self):
        self.son = {}
        self.end = False

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        root = Node()
        for s in dictionary:
            cur = root
            for c in s:
                if c not in cur.son:
                    cur.son[c] = Node()
                cur = cur.son[c]
            cur.end = True
        
        ans = []
        for s in sentence.split():
            cur = root
            pre_flag = False
            for i, c in enumerate(s):
                if cur.end:
                    ans.append(s[:i])
                    pre_flag = True
                    break
                elif c not in cur.son:
                    break
                else:
                    cur = cur.son[c]
            
            if not pre_flag:
                ans.append(s)
        
        return " ".join(ans)