leetcode：648. 单词替换【字典树板子 + 寻找若干前缀中的最短符合前缀】

分析

来个Trie记录字典树
然后一个个单词遍历，用cur去到当前层
如果遍历到某个c，没有在cur中，设置cur[c]为空， cur = cur[c]
结尾的时候来个#表示结束符
然后遍历sentence中的每个单词，如果遍历到#说明匹配到某个前缀了，进行前缀替换
如果发现当前c不在cur中，说明匹配不下去了，直接break

ac code

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # 字典树板子
        trie = {
    }
        for word in dictionary:
            cur = trie
            for c in word:
                # 新增分支
                if c not in cur:
                    cur[c] = {
    }
                cur = cur[c]
            # 结束标志
            cur['#'] = {
    }
        
        words = sentence.split()
        for i in range(len(words)):
            # 在trie寻找最短前缀
            cur = trie
            for j, c in enumerate(words[i]):
                # 匹配到第一个前缀
                if '#' in cur:
                    words[i] = words[i][:j]
                    break
                # 匹配失败
                if c not in cur:
                    break
                # 继续匹配
                cur = cur[c]
        #print(words)
        return ' '.join(words)

总结

字典树板子
可以寻找若干前缀中的最短符合前缀