212.单词搜索 II

字典树 + DFS

使用字典树来存储要查找的单词，字典树的节点中记录单词的搜索路径。

DFS每层把字典树节点传入，就只用在当前节点检查相邻单元格是否在字典树节点的子节点中。

type Trie struct {
    Count int
    Prefix string
    Edges map[byte]*Trie
}

func (this *Trie) Insert(word string)  {
    curr := this
    for i := 0; i < len(word); i++ {
        next, ok := curr.Edges[word[i]]
        if !ok {
            next = &Trie{
                Count: 0,
                Prefix: curr.Prefix + string(word[i]),
                Edges: make(map[byte]*Trie),
            }
            curr.Edges[word[i]] = next
        }

        if i == len(word) - 1 {
            next.Count++
        }

        curr = next

    }
}

func findWords(board [][]byte, words []string) []string {
    m := len(board)
    n := len(board[0])
    ans := []string{}

    tire := &Trie{
        Count: 0,
        Edges: make(map[byte]*Trie),
    }

    for i := 0; i < len(words); i++ {
        tire.Insert(words[i])
    }

    var search func(int, int, *Trie, [][]bool)

    search = func(i, j int, t *Trie, visited [][]bool) {
        if i < 0 || i >= m || j < 0 || j >= n || visited[i][j]{
            return
        }

        dx := []int{0, 1, -1, 0}
        dy := []int{1, 0, 0, -1}

        next, ok := t.Edges[board[i][j]]
        if !ok{
            return
        }

        if next.Count > 0 {
            ans = append(ans, next.Prefix)
            // 字典树中删除该词
            next.Count--
        }

        visited[i][j] = true

        for step := 0; step < 4; step++ {
            search(i+dy[step], j+dx[step], next, visited)
        }

        visited[i][j] = false
    }

    visited := make([][]bool, m)

    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }

    for i, row := range board {
        for j, _ := range row {
            search(i, j, tire, visited)
        }
    }

    return ans
}