1
class Solution {
2
  class TrieNode {
3
    Map<Character, TrieNode> children = new HashMap();
4
    boolean word = false;
5

6
    public TrieNode() {}
7
  }
8

9
  int[][] dirs = new int[][] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
10

11
  public List<String> findWords(char[][] board, String[] words) {
12
    Set<String> res = new HashSet<>();
13
    TrieNode root = new TrieNode();
14
    int m = board.length;
15
    int n = board[0].length;
16

17
    for (String word : words) {
18
      char[] cArr = word.toCharArray();
19
      TrieNode dummy = root;
20

21
      for (char c : cArr) {
22
        if (!dummy.children.containsKey(c)) {
23
          dummy.children.put(c, new TrieNode());
24
        }
25
        dummy = dummy.children.get(c);
26
      }
27

28
      dummy.word = true;
29
    }
30

31
    for (int i = 0; i < m; i++) {
32
      for (int j = 0; j < n; j++) {
33
        char nextChar = board[i][j];
34
        boolean[][] visited = new boolean[m][n];
35
        if (root.children.containsKey(nextChar)) {
36
          res.addAll(dfs(board, root.children.get(nextChar), i, j, visited, "" + nextChar));
37
        }
38
      }
39
    }
40

41
    return new ArrayList<>(res);
42
  }
43

44
  Set<String> dfs(char[][] board, TrieNode root, int i, int j, boolean[][] visited, String word) {
45
    Set<String> res = new HashSet<>();
46

47
    if (root.word) {
48
      res.add(word);
49
      root.word = false;
50
    }
51

52
    visited[i][j] = true;
53

54
    for (int[] dir : dirs) {
55
      int newI = i + dir[0];
56
      int newJ = j + dir[1];
57

58
      if (newI >= 0
59
          && newI < board.length
60
          && newJ >= 0
61
          && newJ < board[0].length
62
          && !visited[newI][newJ]) {
63
        char nextChar = board[newI][newJ];
64
        if (root.children.containsKey(nextChar)) {
65

66
          res.addAll(dfs(board, root.children.get(nextChar), newI, newJ, visited, word + nextChar));
67
        }
68
      }
69
    }
70

71
    visited[i][j] = false;
72

73
    return res;
74
  }
75
}