Daily LeetCode 648. Replace Words

https://leetcode.com/problems/replace-words/

Medium

问题描述：

In English, we have a concept called root, which can be followed by some other words to form another longer word - let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

题目分析：

这一题引用了英语中词根的概念，给定一个dict作为“词根”，例如词根cat，接上tle，就可以组成单词cattle。

我们需要将句子中所有的单词用词根替换，如果字典中有多个词根构成这个单词，那么用最短的词根替换它。

这一题的思路其实很简单，我们采用最暴力的方式，遍历句子中的每个单词，观察这个单词的前缀是否在给定的dict中，若存在则替换。

但这种方式会导致超时问题，在讨论区看到一个优化方法，先将原始给定的dict转换成set，也就是将原来的list转换成set格式。相较于list，查询set的时间复杂度是O(1)，而查询list的时间复杂度是O(n)，因此采用set能够解决超时问题。

代码：

class Solution(object):
    def replaceWords(self, dict, sentence):
        """
        :type dict: List[str]
        :type sentence: str
        :rtype: str
        """
        prefixSet = set(dict)
        
        def successorWord(word):
            for i in range(1, len(word)):
                if word[:i] in prefixSet:
                    return word[:i]
            return word

        return ' '.join(successorWord(word) for word in sentence.split(' '))

前缀树解法：

将dict存放到一个前缀树中，这样我们就可以在线性时间内进行前缀的查询

以题中dict为例，建立的前缀树如图所示：

代码（LeetCode）：

class Solution(object):
    def replaceWords(self, roots, sentence):
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        END = True

        for root in roots:
            cur = trie
            for letter in root:
            		cur = cur[letter]
        		cur[END] = root

    		def replace(word):
        		cur = trie
        		for letter in word:
            		if letter not in cur: 
                  	break
            		cur = cur[letter]
            		if END in cur:
               		 	return cur[END]
        		return word

        return " ".join(map(replace, sentence.split()))