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:
- The input will only have lower-case letters.
- 1 <= dict words number <= 1000
- 1 <= sentence words number <= 1000
- 1 <= root length <= 100
- 1 <= sentence words length <= 1000
Solutions
class Solution {
public String replaceWords(List<String> dict, String sentence) {
Trie root = new Trie();
for (String w : dict) {
root.add(0, w);
}
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));
// reach the end and not found desired root sequence
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.
subTries.get(c).add(i+1, word);
}
public Trie get(Character c) {
return subTries.get(c);
}
}
}