212. Word Search II

time: O(m*n*TrieNode)

space: O(TrieNode)

new version

class Solution {
    class TrieNode {
        Map<Character, TrieNode> sons;
        String word;
        TrieNode() {
            this.sons = new HashMap<>();
            this.word = null;
        }
    }
    
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node.sons.computeIfAbsent(c, v -> new TrieNode());
                node = node.sons.get(c);
            }
            node.word = word;
        }
        return root;
    }
    
    private int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        int m = board.length;
        int n = board[0].length;
        TrieNode node = buildTrie(words);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, node, res);
            }
        }
        return res;
    }
    
    private void dfs(char[][] board, int i , int j, TrieNode node, List<String> res) {
        char c = board[i][j];
        
        TrieNode next = node.sons.get(c);
        if (c == '#' || next == null) {
            return;
        }
        node = next;
        if (node.word != null) {
            res.add(node.word);
            node.word = null;
        }
        board[i][j] = '#';
        for (int dir[] : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (!inArea(board, x , y)) {
                continue;
            }
            dfs(board, x, y, node, res);
        }
        board[i][j] = c;
    }
    
    private boolean inArea(char[][] board, int i , int j) {
        return i >= 0 && i < board.length && j >=0 && j < board[0].length;
    }
}

class Solution {
    private static int DIRECTIONS[][] = new int[][]{{0,1}, {1, 0}, {0, -1}, {-1, 0}};

    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs (board, i, j, root, res);
            }
        }
        return res;
    }
    private void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        char c = board[i][j];
        if (c == '#' || p.next[c - 'a'] == null) return;
        p = p.next[c - 'a'];
        if (p.word != null) {   // found one
            res.add(p.word);
            p.word = null;     // de-duplicate, notice ! set null
        }

        board[i][j] = '#';
        for (int dir[] : DIRECTIONS) {
            dfs(board, i + dir[0], j + dir[1], p, res);  
        }
        board[i][j] = c;
    }

    private TrieNode buildTrie(String[] words) { // O(w), w: words length
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) {
                    p.next[i] = new TrieNode();
                }
                p = p.next[i];
           }
           p.word = w;
        }
        return root;
    }

    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
}