# 648. Replace Words (Medium)

https://leetcode.com/problems/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"

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

## Solutions

class Solution {

public String replaceWords(List<String> dict, String sentence) {
Trie root = new Trie();
for (String w : dict) {
}

String ans = "";
String[] words = sentence.split(" ");
for (String w : words) {
String wx = retrieve(root, w);

ans += wx + " ";
}

// trim off the last blank space
return ans.trim();
}

private String retrieve(Trie root, String word) {
String ans = "";

// pointer of scanning sub tries
Trie trie = root;

// Flag variable, false means the given word does not have any root sequence,
// true means found in the root trie.
boolean isFound = false;

for (int i = 0; i < word.length(); i++) {
trie = trie.get(word.charAt(i));

if (trie == null) {
break;
}

ans += word.charAt(i);

// Exists related root sequence with this word in the dictionary.
if (trie.word != null) {
isFound = true;

break;
}
}

if (!isFound) {
ans = word;
}

return ans;
}

private class Trie {

// From the root Trie node to current one, if the letter sequence forms a word
// existing in the dictionary, then set the word to this variable. Otherwise,
// current sub Trie is not the end of any words in the dictionary and remains null;
String word = null;

// Used to keep sub tries
Map<Character, Trie> subTries = new HashMap<>();

public void add(int i, String word) {
if (i == word.length()) {
this.word = word;

return;
}

Character c = word.charAt(i);
if (!subTries.containsKey(c)) {
subTries.put(c, new Trie());
}

// Add the letters to sub tries recursively.
}

public Trie get(Character c) {
return subTries.get(c);
}
}
}