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,
Givenwords=["oath","pea","eat","rain"]andboard=

[
  ['
o
','
a
','a','n'],
  ['e','
t
','
a
','
e
'],
  ['i','
h
','k','r'],
  ['i','f','l','v']
]

Return

["eat","oath"]

.

Note:
You may assume that all inputs are consist of lowercase lettersa-z.

tag: DFS, Trie

class Solution {
    private class TrieNode{
        TrieNode[] children;
        boolean isWord;
        String val;

        public TrieNode(){
            children = new TrieNode[26];
            isWord = false;
            val = "";
        }

        public void insert(String word, int index){
            if (index == word.length()){
                isWord = true;
                val = word;
                return;
            }

            int pos = word.charAt(index) - 'a';

            if (children[pos] == null){
                children[pos] = new TrieNode();
            }

            children[pos].insert(word, index + 1);
        }

        public TrieNode search(String word, int index){
            if (index == word.length()){
                return this;
            }

            int pos = word.charAt(index) - 'a';

            if (children[pos] == null) return null;

            return children[pos].search(word, index + 1);
        }
    }


    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        if (board == null || words == null) return ans;

        TrieNode root = new TrieNode();
        for (String word : words){
            root.insert(word, 0);
        }

        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                int pos = board[i][j] - 'a';
                if (root.children[pos] != null){

                    dfs(board, i, j, root.children[pos], visited, ans);

                }
            }
        }

        return ans;
    }

    private void dfs(char[][] board, int x, int y, TrieNode root, boolean[][] visited, List<String> ans){
        if (root == null || visited[x][y]) return;

        if (root.isWord && !ans.contains(root.val)){
            //System.out.println("found word: " + root.val);
            ans.add(root.val);
        }

        visited[x][y] = true;

        int[][] moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; i++){
            int xx = x + moves[i][0];
            int yy = y + moves[i][1];
            if (xx < 0 || xx >= board.length || yy < 0 || yy >= board[0].length) continue;

            int newPos = board[xx][yy] - 'a';

            dfs(board, xx, yy, root.children[newPos], visited, ans);
        }

        visited[x][y] = false;
    }
}