648. Replace Words
1. Description
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.
2. Example
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”
3. 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.
4. Solutions
My Accepted Solution
m is the number of letters in i_dictionary, n is the number of letters in i_sentence
Time complexity: O(m)
Space complexity: O(n)
class TrieNode {
public:
array<TrieNode*, 26> childs; // 26 lower case letters
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < childs.size(); ++i) {
childs[i] = nullptr;
}
}
};
class Solution {
public:
// string replaceWords(vector<string>& dictionary, string sentence)
string replaceWords(const vector<string>& i_dictionary, const string& i_sentence) {
TrieNode* trieRoot = new TrieNode();
constructTrieTree(trieRoot, i_dictionary);
string replacedSentence;
stringstream sentenceStream(i_sentence);
for (string word; sentenceStream >> word;) {
replacedSentence += getReplacedWord(trieRoot, word) + " ";
}
if (!replacedSentence.empty() && replacedSentence.back() == ' ') {
replacedSentence.pop_back();
}
return replacedSentence;
}
private:
int getLetterIndex(char letter) {
return letter - 'a';
}
void constructTrieTree(TrieNode* o_trieRoot, const vector<string>& i_dictionary) {
for (auto word : i_dictionary) {
auto iter = o_trieRoot;
for (auto letter : word) {
if (iter->childs[getLetterIndex(letter)] == nullptr) {
iter->childs[getLetterIndex(letter)] = new TrieNode();
}
iter = iter->childs[getLetterIndex(letter)];
}
iter->isEnd = true;
}
}
string getReplacedWord(TrieNode* i_trieRoot, const string& i_word) {
auto iter = i_trieRoot;
string replacedWord = i_word;
for (int i = 0; i < i_word.size(); ++i) {
int letter = i_word[i];
if (iter->isEnd) {
replacedWord = i_word.substr(0, i);
break;
}
if (iter->childs[getLetterIndex(letter)] != nullptr) {
iter = iter->childs[getLetterIndex(letter)];
} else {
break;
}
}
return replacedWord;
}
};