Cacher is the code snippet organizer for pro developers

class TrieNode {
    TrieNode[] children;
    boolean hasWord;
    String word;
    public TrieNode() {
        children = new TrieNode[26];
        hasWord = false;
    }
}


public class Solution {
    public TrieNode buildTrieTree (String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode temp = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (temp.children[idx] == null) temp.children[idx] = new TrieNode();
                temp = temp.children[idx];
            }
            temp.hasWord = true;
            temp.word = word;
        }
        return root;
    }
    
    public void backtracking (char[][] board, int i, int j, TrieNode root, List<String> res) {
        char c = board[i][j];
        if (c == '#' || root.children[c - 'a'] == null) return;
        root = root.children[c - 'a'];
        if (root.hasWord) {
            res.add(root.word);
            root.hasWord = false;
        }
        board[i][j] = '#';
        if (i > 0) backtracking(board, i - 1, j, root, res);
        if (j > 0) backtracking(board, i, j - 1, root, res);
        if (i < board.length - 1) backtracking(board, i + 1, j, root, res);
        if (j < board[0].length - 1) backtracking(board, i, j + 1, root, res);
        board[i][j] = c;
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<String>();
        if (board == null || board.length < 1 || board[0].length < 1 || words == null) return res;
        TrieNode root = buildTrieTree(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                backtracking(board, i, j, root, res);
            }
        }
        return res;
    }
}

public class Solution {
    private class TrieNode{
        TrieNode[] next=new TrieNode[26];
        String w=null;
    }
    private class Trie {
        TrieNode root;
        Trie() {
            root=new TrieNode();
        }
        
        public void add(String s) {
            TrieNode cur=root;
            for(int i=0;i<s.length();i++) {
                char c=s.charAt(i);
                if(cur.next[c-'a']==null) 
                    cur.next[c-'a']=new TrieNode();
                cur=cur.next[c-'a'];
            }
            cur.w=s;
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        List<String> ret=new ArrayList();
        if(board.length==0 || board[0].length==0 || words.length==0) return ret;
        Trie trie=new Trie();
        for(String w:words)
            trie.add(w);
            
        for(int i=0;i<board.length;i++) {
            for(int j=0;j<board[0].length;j++) {
                helper(board,i,j,ret,trie.root);
            }
        }
        return ret;
    }
    
    private void helper(char[][] board, int i, int j, List<String> ret, TrieNode tn) {
        if(board[i][j]=='U') return;
        char c=board[i][j];
        TrieNode curtn=tn.next[c-'a'];
        if(curtn==null) return;
        if(curtn.w!=null) {
            ret.add(curtn.w);
            curtn.w=null;
        }
        
        board[i][j]='U';
        if(i>0) helper(board, i-1,j,ret,curtn);
        if(i<board.length-1) helper(board, i+1,j,ret,curtn);
        if(j>0) helper(board, i,j-1,ret,curtn);
        if(j<board[0].length-1) helper(board, i,j+1,ret,curtn);
        board[i][j]=c;
    }
}