Word Search II

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

public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List <String> res = new ArrayList();
        if(words.length == 0 || board.length == 0) return res;
        // define a Trie
        TrieNode root = new TrieNode();
        // result set
        Set <String> set = new HashSet();
        // keep visited point
        boolean [][]visited = new boolean[board.length][board[0].length];

        // build Trie
        for(String w : words)
            insert(root, w);

        //dfs
        for(int i = 0; i < board.length ; i++)
            for(int j = 0 ; j < board[0].length; j++){
                dfs(set, root, board, visited, i, j, new StringBuilder());
            }

        res.addAll(set);

        return res;
    }

    private void dfs(Set<String> res, TrieNode root, char [][] board, boolean [][] visited, int i, int j, StringBuilder sb){

        if(root == null) return ;

        if(root.isLeaf) res.add(sb.toString());

        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j]){
            return ;
        }

        TrieNode child = root.children.get(board[i][j]);

        visited[i][j] = true;
        sb.append(board[i][j]);

        dfs(res, child, board, visited, i - 1, j, sb);
        dfs(res, child, board, visited, i, j - 1, sb);
        dfs(res, child, board, visited, i + 1, j, sb);
        dfs(res, child, board, visited, i, j + 1, sb);

        visited[i][j] = false;
        sb.deleteCharAt(sb.length() - 1);
    }

    private void insert(TrieNode root, String word){
        TrieNode t = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(t.children.get(c) == null)
                t.children.put(c, new TrieNode());
            t = t.children.get(c);
        }
        t.isLeaf = true;
    }
}

class TrieNode{
    public Map<Character, TrieNode> children;
    public boolean isLeaf = false;
    public TrieNode(){
        children = new HashMap();
    }
}