> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0648-replace-words.md).

# 0648. Replace Words

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

## Description

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.

## ac

```java
class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        TrieNode root = new TrieNode();
        for (String s : dict) {
            build(root, s);
        }

        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            String rt = search(root, words[i]);
            if (rt != null) words[i] = rt;
        }

        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            sb.append(word);
            sb.append(" ");
        }

        return sb.toString().trim();
    }
    private String search(TrieNode node, String word) {
        TrieNode r = node;
        for (int i = 0; i < word.length(); i++) {
            int p = word.charAt(i) - 'a';
            if (r.next[p] == null) return null;
            r = r.next[p];

            // find root, no need to proceed
            if (r.word != null) return r.word;
        }

        return r.word;
    }
    private void build(TrieNode node, String word) {
        TrieNode r = node;
        for (int i = 0; i < word.length(); i++) {
            int p = word.charAt(i) - 'a';
            if (r.next[p] == null) r.next[p] = new TrieNode();
            r = r.next[p];
        }
        r.word = word;
    }
}

class TrieNode {
    TrieNode[] next;
    String word;
    public TrieNode() {
        next = new TrieNode[26];
    }
}
```