-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0212.java
97 lines (79 loc) · 2.63 KB
/
Leetcode0212.java
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package com.netease.music.p20200228;
import com.google.common.collect.Lists;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* Created by dezhonger on 2020/2/28
*/
public class Leetcode0212 {
Set<String> res = new HashSet<>();
int[] dx = new int[]{-1, 0, 1, 0};
int[] dy = new int[]{0, 1, 0, -1};
int m, n;
public static void main(String[] args) {
Leetcode0212 sol = new Leetcode0212();
System.out.println(sol.findWords(new char[][]{
{'o', 'a', 'a', 'n'},
{'e', 't', 'a', 'e'},
{'i', 'h', 'k', 'r'},
{'i', 'f', 'l', 'v'}
}, new String[]{"oath", "pea", "eat", "rain"}));
}
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
build(root, word);
}
m = board.length;
n = board[0].length;
boolean[] v = new boolean[m * n];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (root.children[board[i][j] - 'a'] == null) continue;
v[i * n + j] = true;
dfs(i, j, board, root.children[board[i][j] - 'a'], board[i][j] + "", v);
v[i * n + j] = false;
}
}
return new ArrayList<>(res);
}
private void dfs(int i, int j, char[][] board, TrieNode root, String word, boolean[] v) {
if (root.w == true) {
res.add(word);
}
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
int nxt = board[x][y] - 'a';
if (root.children[nxt] == null) continue;
if (v[x * n + y]) continue;
v[x * n + y] = true;
dfs(x, y, board, root.children[nxt], word + board[x][y], v);
v[x * n + y] = false;
}
}
}
private void build(TrieNode r, String word) {
TrieNode root = r;
char[] ch = word.toCharArray();
for (int i = 0; i < ch.length; i++) {
int t = ch[i] - 'a';
if (root.children[t] == null) {
root.children[t] = new TrieNode();
}
root = root.children[t];
}
root.w = true;
}
class TrieNode {
TrieNode[] children;
boolean w;
public TrieNode() {
this.children = new TrieNode[26];
this.w = false;
}
}
}