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

# Replace Words

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"
```

**Constraints:**

* The input will only have lower-case letters.
* `1 <= dict.length <= 1000`
* `1 <= dict[i].length <= 100`
* 1 <= sentence words number <= 1000
* 1 <= sentence words length <= 1000

```java
class Solution {
    // This is the function called initially
    public String replaceWords(List<String> dict, String sentence) {
        String[] tokens = sentence.split(" ");
        TrieNode trie = buildTrie(dict);
        return replaceWords(tokens, trie);
    }

    private String replaceWords(String[] tokens, TrieNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        for (String token : tokens)
            stringBuilder.append(getShortestReplacement(token, root) + " ");
        // removing last space
        return stringBuilder.substring(0, stringBuilder.length() - 1);
    }

    // Searhing in trie function
    private String getShortestReplacement(String token, final TrieNode root) {
        TrieNode temp = root;
        StringBuilder str = new StringBuilder();
        for (char c : token.toCharArray()) {
            str.append(c);
            if (temp.children[c - 'a'] != null) {
                if (temp.children[c - 'a'].isWord)
                    return str.toString();
                temp = temp.children[c - 'a'];
            } else
                return token;
        }
        return token;
    }

    // Trie building function
    private TrieNode buildTrie(List<String> dict) {
        TrieNode root = new TrieNode(' ');
        for (String word : dict) {
            TrieNode temp = root;
            for (char c : word.toCharArray()) {
                if (temp.children[c - 'a'] == null)
                    temp.children[c - 'a'] = new TrieNode(c);
                temp = temp.children[c - 'a'];
            }
            temp.isWord = true;
        }
        return root;
    }

    public class TrieNode {
        char val;
        TrieNode[] children;
        boolean isWord;

        public TrieNode(char val) {
            this.val = val;
            this.children = new TrieNode[26];
            this.isWord = false;
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://mayanktyagi3111.gitbook.io/interview-prep/trees/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.