forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWord Search II.java
More file actions
60 lines (56 loc) · 1.8 KB
/
Word Search II.java
File metadata and controls
60 lines (56 loc) · 1.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private final int[][] DIRS = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode node = root;
for (Character letter : word.toCharArray()) {
if (node.children.containsKey(letter)) {
node = node.children.get(letter);
} else {
TrieNode newNode = new TrieNode();
node.children.put(letter, newNode);
node = newNode;
}
}
node.word = word;
}
List<String> result = new ArrayList<>();
for (int row = 0; row < board.length; ++row) {
for (int col = 0; col < board[row].length; ++col) {
if (root.children.containsKey(board[row][col])) {
backtracking(row, col, root, result, board);
}
}
}
return result;
}
private void backtracking(int row, int col, TrieNode parent, List<String> result, char[][] board) {
char letter = board[row][col];
TrieNode currNode = parent.children.get(letter);
if (currNode.word != null) {
result.add(currNode.word);
currNode.word = null;
}
board[row][col] = '#';
for (int[] dir : DIRS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow < 0 || newRow >= board.length || newCol < 0 || newCol >= board[0].length) {
continue;
}
if (currNode.children.containsKey(board[newRow][newCol])) {
backtracking(newRow, newCol, currNode, result, board);
}
}
board[row][col] = letter;
if (currNode.children.isEmpty()) {
parent.children.remove(letter);
}
}
private class TrieNode {
Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
String word = null;
public TrieNode() {}
}
}