# LeetCode- Replace Words  Solution
Date: 2021-01-12


### 题目：

In English, we have a concept called **root**, which can be followed by some other word to form another longer word - let's call this word **successor**. For example, when the **root** `"an"` is followed by the **successor** word `"other"`, we can form a new word `"another"`.

Given a `dictionary` consisting of many **roots** and a `sentence` consisting of words separated by spaces, replace all the **successors** in the sentence with the **root** forming it. If a **successor** can be replaced by more than one **root**, replace it with the **root** that has **the shortest length**.

Return _the `sentence`_ after the replacement.

**Example 1:**

**Input:**

```
 dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

```

**Output:**

```
 "the cat was rat by the bat"

```

**Example 2:**

**Input:**

```
 dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

```

**Output:**

```
 "a a b c"

```

**Example 3:**

**Input:**

```
 dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"

```

**Output:**

```
 "a a a a a a a a bbb baba a"

```

**Example 4:**

**Input:**

```
 dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"

```

**Output:**

```
 "the cat was rat by the bat"

```

**Example 5:**

**Input:**

```
 dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"

```

**Output:**

```
 "it is ab that this solution is ac"

```

**Constraints:**

- `1 <= dictionary.length <= 1000`
- `1 <= dictionary[i].length <= 100`
- `dictionary[i]` consists of only lower-case letters.
- `1 <= sentence.length <= 10^6`
- `sentence` consists of only lower-case letters and spaces.
- The number of words in `sentence` is in the range `[1, 1000]`
- The length of each word in `sentence` is in the range `[1, 1000]`
- Each two consecutive words in `sentence` will be separated by exactly one space.
- `sentence` does not have leading or trailing spaces.

### **使用Hash实现**

* * *

  将root存储到使用Hash表， 将要处理的句子拆分后遍历所有单词，通过hash进行判断

- - 时间复杂度O(n²)， 其中n为每个单词匹配到root的长度
    - 空间复杂度O(n)， rootset存放root

- **java实现：**

```
class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        // 定义一个hashset，存放root
        Set<String> rootset = new HashSet<String>();
        for(String root: dictionary) {
            rootset.add(root);
        }
        
        // 将每个单词从sentence中分割出来,        // 存放到一个StringBuilder中
        StringBuilder ans = new StringBuilder();
        
        for (String word: sentence.split("\\s+") ) {
            String prefix="";
            // 判断单词前缀是否在hashset中。 
            for (int i=1; i<=word.length(); i++){
                prefix = word.substring( 0, i);
                if (rootset.contains(prefix)) {
                    break;
                }
            
            }
            if (ans.length() > 0 ) {
                ans.append(" ");
            }
            ans.append(prefix);
                  
        }
        // 返回
        return ans.toString();
     
    }
}
```

- **python实现：**

```
class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        rootset = set(dictionary)
        def replace(word):   
            for i in range(1, len(word)):
                if word[:i] in rootset:
                    return word[:i]
            return word

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

### **使用Trie树实现**

* * *

- -  时间复杂度O(n),   n 为所有字符串长度和， 搜索所有字符串
    - 空间复杂度O(n)，n 为 Trie树空间

- **java实现**

```
class TrieNode {
    TrieNode[] children;
    String word;
    TrieNode(){
        children = new TrieNode[26];
        /*默认初始化null
        for (int i=0; i<26; i++){
            children[i] = null;
        }
        */
    }
}

class Solution{
    public String replaceWords(List<String> dictionary, String sentence) { 
        // 将字典数据存放数Trie树中
        TrieNode trie = new TrieNode();
        for (String root: dictionary) {
            //从头开始遍历
            TrieNode cur =trie;
            for (char letter: root.toCharArray()){
                if (cur.children[letter - 'a'] == null){
                    cur.children[letter - 'a'] = new TrieNode();
                }
                cur = cur.children[letter - 'a'];
            }
            cur.word = root;
        }
        
        // 将句子按照空格分割程单词依次判断是否在Trie树中，
        // 不存在使用原有单词, 完成新句子拼接
        StringBuilder ans = new StringBuilder();
        for (String word: sentence.split("\\s+")){
            if (ans.length() > 0){
                ans.append(" " );
            }
            TrieNode cur = trie;
            for (char letter:word.toCharArray()){
                if (cur.children[letter - 'a'] == null ||\                    cur.word != null){
                    break;
                }
                cur = cur.children[letter - 'a'];
            }
            ans.append(cur.word!=null?cur.word:word);
        }
        return ans.toString();
    }
}
```

- **python实现**：

这个实现使用了python中的collections 的defaultdict容器

 defaultdict内置两个属性：

- 一个工厂函数
- dict

这里Trie定义为一个lambda表达式 ，工厂函数为 collections.defaultdict(Trie),  trie为trie树根节点，那根节点的子节点结构也是一个工厂函数+ dict ，一直到词根的结束增加一条{'END':root} 记录（不一定是叶子节点,可以看到 如果词根是'cat',  存在Key为'True', 如果还存在catx，那么Trie还要向下扩展），如果将'cat'在添加到一个空的Trie树： 过程如下，

1. 增加'c' 字母, defaultdict(<function >, {'c': defaultdict(<function >, {...})})
2. 增加'a' 字母,  1. 中{ ...}  内容->   {'a': defaultdict(<function>, {...})}
3. 增加't' 字母,  2. 中{ ...} 内容->    {'t': defaultdict(<function >, {True: 'cat', ...})}
4. 如果t后面还有字母增加到{...}

reduce函数实现了以上功能， 是对 每一个文根的单个字符进行处理，构造为一个包含defaultdict的defaultdict，自包含， 有点类似树节点定义。   

```
struct Node{
   struct Node *left;
   struct Node *right;
...
};
```

replace就是查找Trie的过程，找到后替换否则保持不变。

```
class Solution: 
    def replaceWords(self, dictionary, sentence):
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        END = True
        
        for root in dictionary:
            reduce(dict.__getitem__, root, trie)[END] = root
        
        def replace(word):
            cur = trie
            for letter in word:
                if letter not in cur or END in cur: break;
                cur = cur[letter]
            return cur.get(END, word)
        
        return " ".join(map(replace, sentence.split()))
```

### 参考及引用：

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

Photo by **[Daniel Spase](https://www.pexels.com/@danielspase?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)** from **[Pexels](https://www.pexels.com/photo/body-of-water-2091351/?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)**