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