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, 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 spearted by spaces. You need to 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 with 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 ans 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 words in sentence will be separted by exactly one space.
sentence doesn't have leading or trailing spaces.
Solution:
class Solution {
static class TrieNode {
char c;
boolean isWord;
TrieNode[] children;
public TrieNode(char c) {
this.c = c;
this.isWord = false;
this.children = new TrieNode[26];
}
}
static class Trie {
TrieNode[] roots;
public Trie() {
roots = new TrieNode[26];
}
public void addWord(String s) {
TrieNode[] nodes = roots;
for (int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
TrieNode curr = nodes[c - 'a'];
if (curr == null) {
curr = new TrieNode(c);
}
if (i == s.length() - 1) {
curr.isWord = true;
}
nodes[c - 'a'] = curr;
nodes = curr.children;
}
}
public String find(String s) {
TrieNode[] nodes = roots;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
TrieNode curr = nodes[c - 'a'];
if (curr == null) {
// System.out.println(c + ", " + s);
return s;
}
sb.append(c);
if (curr.isWord) {
return sb.toString();
}
nodes = curr.children;
}
return s;
}
}
public String replaceWords(List<String> dictionary, String sentence) {
Trie trie = new Trie();
for (String s : dictionary) {
trie.addWord(s);
}
String[] arr = sentence.split(" ");
StringBuilder sb = new StringBuilder();
for (String s : arr) {
String root = trie.find(s);
sb.append(root + " ");
}
sb.setLength(sb.length() - 1);
return sb.toString();
}
}