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:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

Companies:

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")) {
}
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(' ');
}