212
Word Search II
15.1%
Hard

dfs+trie
自定义一个简化版的trie，只需要add
dfs 比较 node.child 和 board[i][j]

public class Solution {
    int m,n;
    ArrayList<String> rst;
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode trieRoot = new TrieNode();
        for (String word:words){
            addWordToTrie(trieRoot, word);
        }
        rst = new ArrayList<String>();
        m = board.length;
        if (m==0) return rst;
        n = board[0].length;
        if (n==0) return rst;
        
        boolean[][] isVisited = new boolean[m][n];
        for (int i=0; i<m; i++)
            for (int j=0; j<n; j++)
                isVisited[i][j] = false;
        for (int i=0; i<m; i++)
            for (int j=0; j<n; j++)
                dfs(board, isVisited, trieRoot, i, j);
        return rst;
    }
    private void dfs(char[][] board, boolean[][] isVisited, TrieNode node, int y, int x){
        if (y<0 || y>=m || x<0 || x>=n || isVisited[y][x]) return;
        int k = board[y][x] - 'a';
        if (node.child[k] == null) return;
        isVisited[y][x] = true;
        if (node.child[k].word != null) {
            rst.add(node.child[k].word);
            node.child[k].word = null;
        }
        dfs(board, isVisited, node.child[k], y, x+1);
        dfs(board, isVisited, node.child[k], y, x-1);
        dfs(board, isVisited, node.child[k], y+1, x);
        dfs(board, isVisited, node.child[k], y-1, x);
        isVisited[y][x] = false;
    }
    private void addWordToTrie(TrieNode root, String word){
        TrieNode p=root;
        for (int i=0; i<word.length(); i++){
            int k = word.charAt(i) - 'a';
            if (p.child[k]==null) p.child[k] = new TrieNode();
            p=p.child[k];
        }
        p.word = word;
    }
}

class TrieNode{
    public TrieNode[] child;
    public String word;
    public TrieNode(){
        child = new TrieNode[26];
    }
}