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.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

一刷
题解：
因为为了要快速判断用dfs构成的prefix是否存在，这里用trie来保存字典。

public class Solution {
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
    
    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> res){
        if(i<0 || j<0 || i>=board.length || j>=board[0].length) return;
        char c = board[i][j];
        if(c == '#' || node.next[c - 'a'] == null) return;
        node = node.next[c-'a'];
        if(node.word!=null){//found
            res.add(node.word);
            node.word = null;
        }
        board[i][j] = '#';
        dfs(board, i-1, j, node, res);
        dfs(board, i+1, j, node, res);
        dfs(board, i, j-1, node, res);
        dfs(board, i, j+1, node, res);
        board[i][j] = c;
    }
    
    
    private TrieNode buildTrie(String[] words){
        TrieNode root = new TrieNode();
        for(String word : words){
            TrieNode node = root;
            for(char ch : word.toCharArray()){
                if(node.next[ch - 'a'] == null){
                    node.next[ch - 'a'] = new TrieNode();
                }
                node = node.next[ch - 'a'];
            }
            node.word = word;
        }
        return root;
    }
}

二刷
这里有两个小细节值得注意，首先TrieNode出了有26个child, 还有一个String field, 可以遍于最后加入list中。
第二，如果遍历到了这个单词，将它置为null， 否则会重复，或者用set保存最终结果。

public class Solution {
    private class TrieNode{
        TrieNode[] child = new TrieNode[26];
        String word;
    }
    
    private TrieNode root = new TrieNode();
    
    public List<String> findWords(char[][] board, String[] words) {
        //buildTree
        List<String> res = new ArrayList<>();
        buildTree(words);
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
    
    
    private void dfs(char[][] board, int i, int j, TrieNode cur, List<String> res){
        if(i<0 || i>=board.length || j<0 || j>=board[0].length) return;
        char ch = board[i][j];
        if(ch == '#' || cur.child[board[i][j] - 'a'] == null) return;
        cur = cur.child[board[i][j] - 'a'];
        if(cur.word != null) {
            res.add(cur.word);
            cur.word = null;
        }
        board[i][j] = '#';
        dfs(board, i+1, j, cur, res);
        dfs(board, i-1, j, cur, res);
        dfs(board, i, j+1, cur, res);
        dfs(board, i, j-1, cur, res);
        board[i][j] = ch;
    }
    
    private void buildTree(String[] words){
        for(String word : words){
            TrieNode cur = root;
            for(int i=0; i<word.length(); i++){
                char ch = word.charAt(i);
                if(cur.child[ch - 'a'] == null){
                    cur.child[ch - 'a'] = new TrieNode();
                }
                cur = cur.child[ch - 'a'];
            }
            cur.word = word;
        }
    }
}