Formatted question description: https://leetcode.ca/all/648.html
648. Replace Words (Medium)
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
Related Topics:
Hash Table, Trie
Solution 1. Trie
// OJ: https://leetcode.com/problems/replace-words/
// Time: O(D + S) where D is size of all contents in dictionary, S is size of all contents in sentence
// Space: O(D)
class TrieNode {
public:
TrieNode *next[26] = {};
bool isWord = false;
};
class Trie {
private:
TrieNode root;
public:
void insert(string &s) {
auto node = &root;
for (char c : s) {
if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
node = node->next[c - 'a'];
}
node->isWord = true;
}
string getWord(string &s) {
auto node = &root;
for (int i = 0; i < s.size(); ++i) {
if (!node->next[s[i] - 'a']) return s;
node = node->next[s[i] - 'a'];
if (node->isWord) return s.substr(0, i + 1);
}
return s;
}
};
class Solution {
public:
string replaceWords(vector<string>& dict, string sentence) {
istringstream ss(sentence);
string word, ans;
Trie trie;
for (auto s : dict) trie.insert(s);
while (ss >> word) ans += trie.getWord(word)+ " ";
ans.pop_back();
return ans;
}
};
Java
class Solution {
TrieNode root = new TrieNode();
public String replaceWords(List<String> dict, String sentence) {
createTrie(dict);
String[] array = sentence.split(" ");
int length = array.length;
for (int i = 0; i < length; i++) {
int prefixLength = searchPrefix(array[i]);
if (prefixLength > 0)
array[i] = array[i].substring(0, prefixLength);
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < length; i++)
sb.append(array[i] + " ");
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
public void createTrie(List<String> dict) {
for (String prefix : dict) {
TrieNode node = root;
int length = prefix.length();
for (int i = 0; i < length; i++) {
char letter = prefix.charAt(i);
int index = letter - 'a';
if (node.next[index] == null)
node.next[index] = new TrieNode();
node = node.next[index];
}
node.isEnd = true;
}
}
public int searchPrefix(String word) {
TrieNode node = root;
int length = word.length();
for (int i = 0; i < length; i++) {
char letter = word.charAt(i);
int index = letter - 'a';
if (node.isEnd)
return i;
else if (node.next[index] == null)
return 0;
else
node = node.next[index];
}
return node.isEnd ? length : 0;
}
}
class TrieNode {
boolean isEnd;
TrieNode[] next;
public TrieNode() {
isEnd = false;
next = new TrieNode[26];
}
}