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
|
package Trie
type Trie struct {
IsWord bool
Buff [26]*Trie
}
func NewNode() *Trie {
return &Trie{false, [26]*Trie{}}
}
/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{false, [26]*Trie{}}
}
/** Inserts a word into the trie. */
func (n *Trie) Insert(word string) {
var p = n
for i, _ := range word {
j := word[i] - 'a'
if p.Buff[j] == nil {
p.Buff[j] = NewNode()
}
p = p.Buff[j]
}
p.IsWord = true
}
/** Returns if the word is in the trie. */
func (n *Trie) Search(word string) bool {
var p = n
for i, _ := range word {
pn := p.Buff[word[i]-'a']
if pn != nil {
p = pn
} else {
return false
}
}
return p.IsWord
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (n *Trie) StartsWith(prefix string) bool {
var p = n
for i, _ := range prefix {
pn := p.Buff[prefix[i]-'a']
if pn != nil {
p = pn
} else {
return false
}
}
return true
}
func FindWords(board [][]byte, words []string) []string {
ret := make([]string, 0, len(words))
tree := NewNode()
for i, _ := range words {
tree.Insert(words[i])
}
retMap := make(map[string]bool, len(words))
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
dsp(tree, board, i, j, "", &retMap)
}
}
for k, _ := range retMap {
ret = append(ret, k)
}
return ret
}
func dsp(tree *Trie, board [][]byte, i int, j int, tmp string, ret *map[string]bool) {
if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] == '#' {
return
}
tmp += string(board[i][j])
if !tree.StartsWith(tmp) {
return
}
if tree.Search(tmp) {
(*ret)[tmp] = true
//*ret = append(*ret, tmp)
}
tmpc := board[i][j]
board[i][j] = '#'
dsp(tree, board, i, j+1, tmp, ret)
dsp(tree, board, i, j-1, tmp, ret)
dsp(tree, board, i+1, j, tmp, ret)
dsp(tree, board, i-1, j, tmp, ret)
board[i][j] = tmpc
}
|