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 derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative 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"
Constraints:
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i] consists of only lower-case letters.1 <= sentence.length <= 106sentence consists of only lower-case letters and spaces.sentence is in the range [1, 1000]sentence is in the range [1, 1000]sentence will be separated by exactly one space.sentence does not have leading or trailing spaces.class Solution {
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
this.children = new TrieNode[26];
this.isEndOfWord = false;
}
}
class Trie {
private final TrieNode root;
public Trie() {
this.root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
node.children[idx] = new TrieNode();
node = node.children[idx];
}
node.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
return false;
node = node.children[idx];
}
return node.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null)
return false;
node = node.children[idx];
}
return true;
}
public String findRoot(String word) {
TrieNode node = root;
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; i++) {
int idx = chars[i] - 'a';
if (node.children[idx] == null)
return word;
node = node.children[idx];
if (node.isEndOfWord)
return word.substring(0, i + 1);
}
return word;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
public String replaceWords(List<String> dictionary, String sentence) {
String[] words = sentence.split(" ");
Trie dict = new Trie();
for (String word : dictionary)
dict.insert(word);
for (int i = 0; i < words.length; i++)
words[i] = dict.findRoot(words[i]);
return String.join(" ", words);
}
}