648.单词替换

648. 单词替换

一、直接法

class Solution:
    def replaceWords(self, dictionary, sentence) -> str:
        dicSet = set(dictionary)	#字典转集合
        wordList = sentence.split(' ')	#先将句子切分为单词
		# 遍历每个单词
        for i, word in enumerate(wordList):
            # 从长度为1开始截取单词（保证最短），看是否匹配字典中的词
            #只要匹配，就用截取的部分替换
            for j in range(1, len(word)+1):
                if word[:j] in dicSet:
                    wordList[i] = word[:j]
                    break

        return " ".join(wordList)

二、前缀树

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, word in enumerate(words):
            cur = trie
            for j, c in enumerate(word):
                if '#' in cur:
                    words[i] = word[:j]
                    break
                if c not in cur:
                    break
                cur = cur[c]
        return ' '.join(words)