212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input:
words = [“oath”,”pea”,”eat”,”rain”] and board =
[
[‘o’,’a’,’a’,’n’],
[‘e’,’t’,’a’,’e’],
[‘i’,’h’,’k’,’r’],
[‘i’,’f’,’l’,’v’]
]

Output: [“eat”,”oath”]
Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution

Tire + BackTracing
先构建字典树,然后dfs查找答案

corner case:

  1. 重复word
  2. 多次访问路径上的字符

优化点:

  1. w.toCharArray() instead of w.charAt(i)
  2. 防止res加入重复word, 可在第一次加入后将TireNode.word至空
  3. 取消visited数组,直接修改board数组

Code

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 TrieNode {
String word;
TrieNode[] links;

public TrieNode() {
word = "";
links = new TrieNode[26];
}
}

public List<String> findWords(char[][] board, String[] words) {
if (board == null || board.length == 0) return new ArrayList<>();
TrieNode root = generate(words);
Set<String> res = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
char tmp = board[i][j];
boolean[][] visited = new boolean[board.length][board[0].length];
visited[i][j] = true;
dfs(i, j, root.links[tmp - 'a'], visited,board, res);
visited[i][j] = false;
}
}
return new ArrayList<>(res);
}

public void dfs(int x, int y, TrieNode node, boolean[][] visited, char[][] board, Set<String> res) {
if (node == null) return;
if (!node.word.equals("")) res.add(node.word);

int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < dir.length; i++) {
int new_x = x + dir[i][0];
int new_y = y + dir[i][1];
if (new_x >= 0 && new_x < board.length && new_y >= 0 && new_y < board[0].length && !visited[new_x][new_y]) {
char tmp = board[new_x][new_y];
visited[new_x][new_y] = true;
dfs(new_x, new_y, node.links[tmp - 'a'], visited, board, res);
visited[new_x][new_y] = false;
}

}

}

public TrieNode generate(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
TrieNode curr = root;
for (int j = 0; j < word.length(); j++) {
char tmp = word.charAt(j);
if (curr.links[tmp - 'a'] == null) {
curr.links[tmp - 'a'] = new TrieNode();
}
curr = curr.links[tmp - 'a'];
}
curr.word = word;
}
return root;
}