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

type Trie struct {
    children	map[rune] *Trie 
    isEnd		bool
}


func Constructor() Trie {
    return Trie{children: make(map[rune]*Trie)}
}


func (this *Trie) Insert(word string)  {
    cur := this
    for _, ch := range word{
        if cur.children[ch] == nil{
            cur.children[ch] = &Trie{children: make(map[rune]*Trie)}
        }
        cur = cur.children[ch]
    }
    cur.isEnd = true
}


func (this *Trie) Search(word string) bool {
    cur := this 
    for _, ch := range word{
        if cur.children[ch] == nil{
            return false 
        }
        cur = cur.children[ch]
    }
    return cur.isEnd
}


func (this *Trie) StartsWith(prefix string) bool {
    cur := this 
    for _, ch := range prefix{
        if cur.children[ch] == nil{
            return false 
        }
        cur = cur.children[ch]
    }
    return true
}

 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

type WordDictionary struct {
    Next	map[rune]*WordDictionary
    End		bool 
}


func Constructor() WordDictionary {
    return WordDictionary{
        Next: make(map[rune]*WordDictionary),
    }
}


func (this *WordDictionary) AddWord(word string)  {
    cur := this
    for _, v := range word{
        if cur.Next[v] == nil{
            cur.Next[v] = &WordDictionary{
                Next: make(map[rune]*WordDictionary),
            }
        }
        cur = cur.Next[v]
    }
    cur.End = true
}


func (this *WordDictionary) Search(word string) bool {
    cur := this 
    for k, v := range word{
        switch{
        case v == '.':
            res := false
            for _, nxt := range cur.Next{
                res = res || nxt.Search(word[k+1:])
            }
            return res
        case cur.Next[v] == nil:
            return false
        default:
            cur = cur.Next[v]
        }
    }
    return cur.End
}

 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

func findWords(board [][]byte, words []string) []string {

    // Step1: 定义Trie树结构
    type Trie struct{
        Son		map[byte]*Trie
        Str		string
    }

    // Step2: 构建这棵树
    root := &Trie{Son: make(map[byte]*Trie)}
    for _, word := range words{
        cur := root 
        for idx := range word{
            char := word[idx]
            if cur.Son[char] == nil{
                cur.Son[char] = &Trie{
                    Son: make(map[byte]*Trie),
                }
            }
            cur = cur.Son[char]
        }
        cur.Str = word
    }

    // Step3: 定义对于一个坐标的搜索dfs函数
    m, n := len(board), len(board[0])
    res := make([]string, 0)

    // 定义很重要啊
    // x, y：定位板上的当前位置。
    // cur：当前匹配到的Trie节点，记录已匹配的路径。
    // nxt：下一个可能的Trie节点，基于当前字符决定是否继续搜索。
    var dfs func(int, int, *Trie)
    dfs = func(x, y int, cur *Trie){
        
        // 合法性判断：出界或者已访问
        if x < 0 || y < 0 || x == m || y == n{
            return 
        }else if board[x][y] == '#'{
            return 
        }

        char := board[x][y]
        nxt := cur.Son[char]

        // 到头判定：这里有个已经被找到的
        if nxt == nil{
            return 
        }
        // 发现判定：找到，记录这个，继续不要停
        if nxt.Str != ""{
            res = append(res, nxt.Str)
            nxt.Str = ""
        }

        // 标准dfs搜索代码
        board[x][y] = '#'
        dfs(x+1, y, nxt)
        dfs(x-1, y, nxt)
        dfs(x, y+1, nxt)
        dfs(x, y-1, nxt)
        board[x][y] = char
    }

    // Step4: 对每个位置运行dfs搜索
    for i := 0; i < m; i++{
        for j := 0; j < n; j++{
            dfs(i, j, root)
        }
    }

    return res
}