Word Search II

1class TrieNode {
2    Map<Character, TrieNode> children = new HashMap<>();
3    String word = null;
4}
5
6public List<String> findWords(char[][] board, String[] words) {
7    // Build Trie
8    TrieNode root = new TrieNode();
9    for (String word : words) {
10        TrieNode node = root;
11        for (char c : word.toCharArray()) {
12            if (!node.children.containsKey(c)) {
13                node.children.put(c, new TrieNode());
14            }
15            node = node.children.get(c);
16        }
17        node.word = word;
18    }
19
20    int rows = board.length;
21    int cols = board[0].length;
22    List<String> result = new ArrayList<>();
23    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
24
25    for (int r = 0; r < rows; r++) {
26        for (int c = 0; c < cols; c++) {
27            if (root.children.containsKey(board[r][c])) {
28                dfs(r, c, root.children.get(board[r][c]), board, result, dirs, rows, cols);
29            }
30        }
31    }
32
33    return result;
34}
35
36private void dfs(int r, int c, TrieNode node, char[][] board, List<String> result, int[][] dirs, int rows, int cols) {
37    if (node.word != null) {
38        result.add(node.word);
39        node.word = null;
40    }
41
42    char ch = board[r][c];
43    board[r][c] = '#';
44
45    for (int[] dir : dirs) {
46        int nr = r + dir[0];
47        int nc = c + dir[1];
48        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#') {
49            char nextChar = board[nr][nc];
50            if (node.children.containsKey(nextChar)) {
51                dfs(nr, nc, node.children.get(nextChar), board, result, dirs, rows, cols);
52            }
53        }
54    }
55
56    board[r][c] = ch;
57}