-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
648. Replace Words.go
102 lines (92 loc) · 1.96 KB
/
648. Replace Words.go
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package leetcode
import "strings"
// 解法一 哈希表
func replaceWords(dict []string, sentence string) string {
roots := make(map[byte][]string)
for _, root := range dict {
b := root[0]
roots[b] = append(roots[b], root)
}
words := strings.Split(sentence, " ")
for i, word := range words {
b := []byte(word)
for j := 1; j < len(b) && j <= 100; j++ {
if findWord(roots, b[0:j]) {
words[i] = string(b[0:j])
break
}
}
}
return strings.Join(words, " ")
}
func findWord(roots map[byte][]string, word []byte) bool {
if roots[word[0]] == nil {
return false
}
for _, root := range roots[word[0]] {
if root == string(word) {
return true
}
}
return false
}
// 解法二 Trie
func replaceWords1(dict []string, sentence string) string {
trie := Constructor208()
for _, v := range dict {
trie.Insert(v)
}
words := strings.Split(sentence, " ")
var result []string
word := ""
i := 0
for _, value := range words {
word = ""
for i = 1; i < len(value); i++ {
if trie.Search(value[:i]) {
word = value[:i]
break
}
}
if len(word) == 0 {
result = append(result, value)
} else {
result = append(result, word)
}
}
return strings.Join(result, " ")
}
type Trie struct {
isWord bool
children map[rune]*Trie
}
/** Initialize your data structure here. */
func Constructor208() Trie {
return Trie{isWord: false, children: make(map[rune]*Trie)}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
parent := this
for _, ch := range word {
if child, ok := parent.children[ch]; ok {
parent = child
} else {
newChild := &Trie{children: make(map[rune]*Trie)}
parent.children[ch] = newChild
parent = newChild
}
}
parent.isWord = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
parent := this
for _, ch := range word {
if child, ok := parent.children[ch]; ok {
parent = child
continue
}
return false
}
return parent.isWord
}