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構(gòu)成的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;
    }
}

二刷
這里有兩個小細節(jié)值得注意瘦材，首先TrieNode出了有26個child, 還有一個String field, 可以遍于最后加入list中等限。
第二迟郎，如果遍歷到了這個單詞坎弯，將它置為null厦坛， 否則會重復(fù)露该，或者用set保存最終結(jié)果睬棚。

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;
        }
    }
}