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

lc212

class Solution {
    private static final int SIZE = 26;
    private static final int[][] DIRECTIONS = new int[][] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    private static final char VISITED_CHAR = '*';
    
    
    // Time: O(mn*3^k)
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> result = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                searchAndAddWords(board, i, j, root, result);       
            }
        }
        return result;
    }
    
    // Time: O(3^k), where k = the depth of the Trie
    // Space: O(max(k, L)), where L is the number of words
    private void searchAndAddWords(char[][] board, int i, int j, TrieNode parent, List<String> res) {
        assert board != null;
        assert parent != null;
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] == VISITED_CHAR) {
            return;
        }
        char currLetter = board[i][j];
        TrieNode currNode = parent.children[currLetter - 'a'];
        if (currNode == null) {
            return;
        }
        board[i][j] = VISITED_CHAR;
        if (currNode.word != null) {
            res.add(currNode.word);
            // a trick to de-dup paths to the same word
            currNode.word = null;
        }
        for (int[] direction : DIRECTIONS) {
            searchAndAddWords(board, i + direction[0], j + direction[1], currNode, res);
        }
        board[i][j] = currLetter;
    }
    
    static class TrieNode {
        String word;
        TrieNode[] children = new TrieNode[SIZE];
    }
    
    private static TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
           TrieNode curr = root;
           for (int i = 0; i < w.length(); i++) {
               int idx = w.charAt(i) - 'a';
               if (curr.children[idx] == null) {
                   curr.children[idx] = new TrieNode();
               }
               curr = curr.children[idx];
           }
           curr.word = w;
        }
        return root;
    }
}