Trie - 212. Word Search II

212. Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

思路：

题目意思是给一个棋盘里面有很多字母，再给一个系列字符串，返回能在棋盘中找到的字符串。在棋盘中找字符串很明显使用dfs来做，匹配不到字符串的某个字母来进行剪枝。另外使用trie来对字符串收缩进行加速。

代码：

go：

const R = 26


type TrieNode struct {
    Children [R]*TrieNode
    word string
}

func findWords(board [][]byte, words []string) []string {
    var res []string
    if board == nil || len(board) == 0 || len(board[0]) == 0 {
        return res
    } 
    
    root := buidlTrie(words)
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            dfs(board, i, j, root, &res)
        }
    }
    
    return res
}

func dfs(board [][]byte, i, j int, p *TrieNode, res *[]string) {
    c := board[i][j]
    if (c == '#' || p.Children[c - 'a'] == nil) {return}
    
    p = p.Children[c - 'a']
    if (p.word != "") {   // found one
        *res = append(*res, p.word)
        p.word = ""     // de-duplicate
    }

    board[i][j] = '#'
    if i > 0 {
        dfs(board, i - 1, j ,p, res)  
    }  
    if j > 0 {
        dfs(board, i, j - 1, p, res)
    }
    if i < len(board) - 1 {
        dfs(board, i + 1, j, p, res)
    }
    if j < len(board[0]) - 1 {
        dfs(board, i, j + 1, p, res)
    }
    board[i][j] = c;
}


func buidlTrie(words []string) *TrieNode {
    root := &TrieNode{Children:[R]*TrieNode{}}
    for _, w := range  words {
        p := root;
        for i := 0; i < len(w); i++ {
            c := rune(w[i])
            idx := c - 'a'
            if p.Children[idx] == nil {
                p.Children[idx] = &TrieNode{Children:[R]*TrieNode{}}
            }
            p = p.Children[idx]
       }
       p.word = w;
    }
    return root;
}