Approach: Backtracking with Trie1
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
96
97
98class Solution {
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res, int[][] dir) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = '#';
for(int[] d:dir){
dfs(board, i+d[0], j+d[1], p, res, dir);
}
board[i][j] = c;
}
public List<String> findWords(char[][] board, String[] words) {
int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, root, res, dir);
}
}
return res;
}
}
/*
class Solution {
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j, p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
board[i][j] = c;
}
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs(board, i, j, root, res);
}
}
return res;
}
}*/
Approach: Backtracking1
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// Accepted
class Solution {
private int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
private Set<String> res = new HashSet<>();
private void dfs(char[][] board, int i, int j, String word, int pos, boolean[][] seen) {
if (pos == word.length()) {
res.add(word);
return;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || seen[i][j] || board[i][j] != word.charAt(pos)) return;
seen[i][j] = true;
for (int[] d : dir) {
dfs(board, i + d[0], j + d[1], word, pos + 1, seen);
}
seen[i][j] = false;
}
public List<String> findWords(char[][] board, String[] words) {
int R = board.length, C = board[0].length;
for (String word : words) {
boolean[][] seen = new boolean[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
dfs(board, i, j, word, 0, seen);
}
}
}
return new ArrayList<String>(res);
}
}
// Time Limit Exceeded
/*
class Solution {
private int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
private Set<String> res = new HashSet<>();
private void dfs(char[][] board, int i, int j, String word, StringBuilder tmp, boolean[][] seen) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
if (!seen[i][j]) {
tmp.append(board[i][j]);
if (tmp.toString().equals(word)) {
res.add(word);
}
seen[i][j] = true;
for (int[] d : dir) {
int i_next = i + d[0];
int j_next = j + d[1];
dfs(board, i_next, j_next, word, tmp, seen);
}
tmp.deleteCharAt(tmp.length() - 1);
seen[i][j] = false;
}
}
public List<String> findWords(char[][] board, String[] words) {
int R = board.length, C = board[0].length;
for (String word : words) {
StringBuilder tmp = new StringBuilder();
boolean[][] seen = new boolean[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
dfs(board, i, j, word, tmp, seen);
}
}
}
return new ArrayList<String>(res);
}
}*/