Welcome to Subscribe On Youtube
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;
}
};
-
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]; } } ############ class Trie { Trie[] children = new Trie[26]; String v; void insert(String word) { Trie node = this; for (char c : word.toCharArray()) { c -= 'a'; if (node.children[c] == null) { node.children[c] = new Trie(); } node = node.children[c]; } node.v = word; } String search(String word) { Trie node = this; for (char c : word.toCharArray()) { c -= 'a'; if (node.children[c] == null) { return word; } node = node.children[c]; if (node.v != null) { return node.v; } } return word; } } class Solution { public String replaceWords(List<String> dictionary, String sentence) { Trie trie = new Trie(); for (String v : dictionary) { trie.insert(v); } List<String> ans = new ArrayList<>(); for (String v : sentence.split("\\s")) { ans.add(trie.search(v)); } return String.join(" ", ans); } } -
// 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; } }; -
class Trie: def __init__(self): self.children = [None] * 26 self.v = None def insert(self, word): node = self for c in word: idx = ord(c) - ord('a') if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.v = word def search(self, word): node = self for c in word: idx = ord(c) - ord('a') if node.children[idx] is None: break node = node.children[idx] if node.v: return node.v return word class Solution: def replaceWords(self, dictionary: List[str], sentence: str) -> str: trie = Trie() for v in dictionary: trie.insert(v) return ' '.join(trie.search(v) for v in sentence.split()) ############ class TrieNode(object): def __init__(self): self.children = {} self.isWord = False self.word = "" class Solution(object): def replaceWords(self, dict, sentence): """ :type dict: List[str] :type sentence: str :rtype: str """ root = TrieNode() for word in dict: p = root for c in word: if c not in p.children: p.children[c] = TrieNode() p = p.children[c] p.isWord = True p.word = word words = sentence.split() for i in range(len(words)): p = root for c in words[i]: if c in p.children: p = p.children[c] if p.isWord: words[i] = p.word break else: break return " ".join(words) -
type Trie struct { children [26]*Trie v string } func newTrie() *Trie { return &Trie{} } func (this *Trie) insert(word string) { node := this for _, c := range word { c -= 'a' if node.children[c] == nil { node.children[c] = newTrie() } node = node.children[c] } node.v = word } func (this *Trie) search(word string) string { node := this for _, c := range word { c -= 'a' if node.children[c] == nil { break } node = node.children[c] if node.v != "" { return node.v } } return word } func replaceWords(dictionary []string, sentence string) string { trie := newTrie() for _, v := range dictionary { trie.insert(v) } var ans []string for _, v := range strings.Split(sentence, " ") { ans = append(ans, trie.search(v)) } return strings.Join(ans, " ") } -
class Trie { private children: Trie[]; private ref: number; constructor() { this.children = new Array<Trie>(26); this.ref = -1; } public insert(w: string, i: number) { let node: Trie = this; for (const c of w) { const idx = c.charCodeAt(0) - 97; if (!node.children[idx]) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.ref = i; } public search(w: string): number { let node: Trie = this; for (const c of w) { const idx = c.charCodeAt(0) - 97; if (!node.children[idx]) { return -1; } node = node.children[idx]; if (node.ref !== -1) { return node.ref; } } return -1; } } function replaceWords(dictionary: string[], sentence: string): string { const trie = new Trie(); for (let i = 0; i < dictionary.length; i++) { trie.insert(dictionary[i], i); } return sentence .split(' ') .map(w => { const idx = trie.search(w); return idx !== -1 ? dictionary[idx] : w; }) .join(' '); }