# 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];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0648-replace-words.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.