leetcode648. 单词替换

思路：
遍历句子里的所有单词，再遍历这个单词判断是不是有词根有的话替换跳出循环

def replaceWords(self, dictionary, sentence):
        """
        :type dictionary: List[str]
        :type sentence: str
        :rtype: str
        """
        visit = set(dictionary)
        words  = sentence.split(" ")
        for  i, word in enumerate(words):
            for j in range(1,len(word)+1):
                if word[:j] in visit:
                    words[i] = word[:j]
                    break
        return " ".join(words)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

字典树

class Tire(object):
    def __init__(self):
        self.children = {}
        self.flag = False
    def insert(self,word):
        root = self
        for ch in word:
            if ch not in root.children:
                root.children[ch] = Tire()
            root = root.children[ch]
        root.flag = True

    def search(self,word):
        node = self
        for i,ch in enumerate(word):
            if  ch not in node.children:
                return False
            node = node.children[ch]          #因为是从根节点开始，所以应该要后移一位再判断
            if node.flag:
                return word[:i+1]
            
class Solution(object):
    def replaceWords(self, dictionary, sentence):
        """
        :type dictionary: List[str]
        :type sentence: str
        :rtype: str
        """
        tire = Tire()
        words = sentence.split(" ")
        for word in dictionary:
            tire.insert(word)
        for i,word in enumerate(words):
            if tire.search(word):
                words[i] = tire.search(word)
        return " ".join(words)
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
35
36