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.
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"
Constraints:
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i] consists of only lower-case letters.1 <= sentence.length <= 106sentence 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] - Every two consecutive words in
sentence will be separated by exactly one space. sentence does not have leading or trailing spaces.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Trie:
def __init__(self):
self.children: List[Trie | None] = [None] * 26
self.ref: int = -1
def insert(self, w: str, i: int):
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.ref = i
def search(self, w: str) -> int:
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
return -1
node = node.children[idx]
if node.ref != -1:
return node.ref
return -1
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
trie = Trie()
for i, w in enumerate(dictionary):
trie.insert(w, i)
ans = []
for w in sentence.split():
idx = trie.search(w)
ans.append(dictionary[idx] if idx != -1 else w)
return " ".join(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Set<String> s = new HashSet<>(dictionary);
String[] words = sentence.split(" ");
for (int i = 0; i < words.length; ++i) {
String word = words[i];
for (int j = 1; j <= word.length(); ++j) {
String t = word.substring(0, j);
if (s.contains(t)) {
words[i] = t;
break;
}
}
}
return String.join(" ", words);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| class Trie {
private:
Trie* children[26];
int ref;
public:
Trie()
: ref(-1) {
memset(children, 0, sizeof(children));
}
void insert(const string& w, int i) {
Trie* node = this;
for (auto& c : w) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new Trie();
}
node = node->children[idx];
}
node->ref = i;
}
int search(const string& w) {
Trie* node = this;
for (auto& c : w) {
int idx = c - 'a';
if (!node->children[idx]) {
return -1;
}
node = node->children[idx];
if (node->ref != -1) {
return node->ref;
}
}
return -1;
}
};
class Solution {
public:
string replaceWords(vector<string>& dictionary, string sentence) {
Trie* trie = new Trie();
for (int i = 0; i < dictionary.size(); ++i) {
trie->insert(dictionary[i], i);
}
stringstream ss(sentence);
string w;
string ans;
while (ss >> w) {
int idx = trie->search(w);
ans += (idx == -1 ? w : dictionary[idx]) + " ";
}
ans.pop_back();
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| type Trie struct {
children [26]*Trie
ref int
}
func newTrie() *Trie {
return &Trie{ref: -1}
}
func (this *Trie) insert(w string, i int) {
node := this
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = newTrie()
}
node = node.children[idx]
}
node.ref = i
}
func (this *Trie) search(w string) int {
node := this
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
return -1
}
node = node.children[idx]
if node.ref != -1 {
return node.ref
}
}
return -1
}
func replaceWords(dictionary []string, sentence string) string {
trie := newTrie()
for i, w := range dictionary {
trie.insert(w, i)
}
ans := strings.Builder{}
for _, w := range strings.Split(sentence, " ") {
if idx := trie.search(w); idx != -1 {
ans.WriteString(dictionary[idx])
} else {
ans.WriteString(w)
}
ans.WriteByte(' ')
}
return ans.String()[:ans.Len()-1]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| 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(' ');
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Trie {
private Trie[] children = new Trie[26];
private int ref = -1;
public void insert(String w, int i) {
Trie node = this;
for (int j = 0; j < w.length(); ++j) {
int idx = w.charAt(j) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.ref = i;
}
public int search(String w) {
Trie node = this;
for (int j = 0; j < w.length(); ++j) {
int idx = w.charAt(j) - 'a';
if (node.children[idx] == null) {
return -1;
}
node = node.children[idx];
if (node.ref != -1) {
return node.ref;
}
}
return -1;
}
}
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Trie trie = new Trie();
for (int i = 0; i < dictionary.size(); ++i) {
trie.insert(dictionary.get(i), i);
}
List<String> ans = new ArrayList<>();
for (String w : sentence.split("\\s")) {
int idx = trie.search(w);
ans.add(idx == -1 ? w : dictionary.get(idx));
}
return String.join(" ", ans);
}
}
|
