LeetCode- Replace Words Solution

题目：

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) {
}

// 将每个单词从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实现

defaultdict内置两个属性：

• 一个工厂函数
• dict

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 from Pexels