https://leetcode.com/problems/word-search-ii/

word-search-ii.java

class Solution {
    class TrieNode {
        char c;
        String word;
        TrieNode[] children;
        boolean isWord;
        
        public TrieNode(char c) {
            this.c = c;
            this.children = new TrieNode[26];
            this.isWord = false;
        }
    }
    
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (board.length == 0 || board[0].length == 0 || words.length == 0) {
            return result;
        }
        TrieNode root = buildTrie(words);
        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                search(result, board, visited, root, i, j);
            }
        }
        return result;
    }
    
    
    
    public boolean search(List<String> result, char[][] board, boolean[][] visited, TrieNode node, int x, int y) {
        int r = board.length;
        int c = board[0].length;
        
        if (visited[x][y]) {
            return false; // visiting
        }
        
        char ch = board[x][y];
        if (node.children[ch - 'a'] == null) {
            return false;
        }
        TrieNode currNode = node.children[ch - 'a'];
        if (currNode.isWord) {
            currNode.isWord = false;
            result.add(currNode.word);
        }
        visited[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            search(result, board, visited, currNode, nx, ny);
        }
        visited[x][y] = false;
        return true;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode('#');
        for (String w : words) {
            insert(root, w);
        }
        return root;
    }
    
    public void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode(c);
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
        node.word = word;
    }
    
    
}