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
61
62
63
64
| class Solution {
private static class TrieNode {
Map<Character, TrieNode> children;
String word;
TrieNode() {
this.children = new HashMap<>();
word = null;
}
}
private void addWord(String word, TrieNode root) {
TrieNode ptr = root;
for (char letter : word.toCharArray()) {
ptr.children.putIfAbsent(letter, new TrieNode());
ptr = ptr.children.get(letter);
}
ptr.word = word;
}
private int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
public List<String> findWords(char[][] board, String[] words) {
List<String> ans = new ArrayList<>();
TrieNode root = new TrieNode();
for (String word : words) {
addWord(word, root);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (root.children.containsKey(board[i][j])) {
backtrack(board, ans, i, j, root);
}
}
}
return ans;
}
private void backtrack(char[][] board, List<String> ans, int row, int col, TrieNode parent) {
char currLetter = board[row][col];
TrieNode currNode = parent.children.get(currLetter);
if (currNode.word != null) {
ans.add(currNode.word);
currNode.word = null;
}
board[row][col] = '#';
for (int[] direction : directions) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (!isOutOfBound(board.length, board[0].length, newRow, newCol)
&& currNode.children.containsKey(board[newRow][newCol])) {
backtrack(board, ans, newRow, newCol, currNode);
}
}
board[row][col] = currLetter;
if (currNode.children.isEmpty()) {
parent.children.remove(currLetter);
}
}
private boolean isOutOfBound(int rowSize, int colSize, int row, int col) {
return row < 0 || row >= rowSize || col < 0 || col >= colSize;
}
}
|
