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"].

一刷
題解：
因?yàn)闉榱艘焖倥袛嘤胐fs構(gòu)成的prefix是否存在，這里用trie來(lái)保存字典。

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

二刷
這里有兩個(gè)小細(xì)節(jié)值得注意，首先TrieNode出了有26個(gè)child, 還有一個(gè)String field, 可以遍于最后加入list中。
第二，如果遍歷到了這個(gè)單詞，將它置為null， 否則會(huì)重復(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;
        }
    }
}