# 648 Replace Words

## 648. [Replace Words](https://leetcode.com/problems/replace-words/description/)

## 1. Question

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

## 2. Implementation

**(1) Trie**

思路: 很典型的查询prefix的应用，所以用trie很适合，只要在trieNode的基础上加入字典里的string所对应的index即可

```java
class Solution {
    class TrieNode {
        char val;
        int index;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val) {
            this.val = val;
            index = -1;
            childNode = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void insert(String word, int index) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int pos = c - 'a';
                if (curNode.childNode[pos] == null) {
                    curNode.childNode[pos] = new TrieNode(c);
                }
                curNode = curNode.childNode[pos];
            }
            curNode.isWord = true;
            curNode.index = index;
        }

        public int searchPrefix(String word) {
            if (word == null || word.length() == 0) {
                return -1;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int pos = c - 'a';
                if (curNode.childNode[pos] == null) {
                    return -1;
                }
                else if (curNode.childNode[pos].isWord){
                    return curNode.childNode[pos].index;
                }
                curNode = curNode.childNode[pos];
            }
            return curNode.index;
        }
    }
    public String replaceWords(List<String> dict, String sentence) {
        if (dict.size() == 0 || sentence == null || sentence.length() == 0) {
            return "";
        }

        Trie trie = new Trie();

        for (int i = 0; i < dict.size(); i++) {
            trie.insert(dict.get(i), i);
        }

        String[] words = sentence.split("\\s+");

        for (int i = 0; i < words.length; i++) {
            int index = trie.searchPrefix(words[i]);

            if (index != -1) {
                words[i] = dict.get(index);
            }
        }

        StringBuilder res = new StringBuilder();

        for (int i = 0; i < words.length - 1; i++) {
            res.append(words[i]);
            res.append(" ");
        }

        res.append(words[words.length - 1]);
        return res.toString();
    }
}
```

## 3. Time & Space Complexity

**Trie:** 时间复杂度O(n \* m), n是dict里面string的个数，m是string的平均长度。 空间复杂度O(nm)