Skip to content

Commit d416d34

Browse files
fishercoder1534fishercoder1534
committed
refactor 212
1 parent 3dd8ae4 commit d416d34

File tree

2 files changed

+61
-19
lines changed

2 files changed

+61
-19
lines changed

‎src/main/java/com/fishercoder/solutions/_212.java

Lines changed: 19 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -19,31 +19,32 @@ public List<String> findWords(char[][] board, String[] words) {
1919
}
2020

2121
private void dfs(TrieNode root, char[][] board, int i, int j, List<String> result) {
22-
char c = board[i][j];
22+
char tmp = board[i][j];
2323

24-
if (c == '#' || root.children[c - 'a'] == null) {
24+
if (tmp == '#' || root.children[tmp - 'a'] == null) {
2525
return;
2626
}
2727

28-
if (root.children[c - 'a'].word != null) {
29-
result.add(root.children[c - 'a'].word);
30-
root.children[c - 'a'].word = null;//de-duplicate
28+
if (root.children[tmp - 'a'].word != null) {
29+
result.add(root.children[tmp - 'a'].word);
30+
root.children[tmp - 'a'].word = null;//de-duplicate
3131
}
3232
board[i][j] = '#';//mark it as visited to avoid cycles
3333
if (i > 0) {
34-
dfs(root.children[c - 'a'], board, i - 1, j, result);
34+
dfs(root.children[tmp - 'a'], board, i - 1, j, result);
3535
}
3636
if (j > 0) {
37-
dfs(root.children[c - 'a'], board, i, j - 1, result);
37+
dfs(root.children[tmp - 'a'], board, i, j - 1, result);
3838
}
3939
if (i + 1 < board.length) {
40-
dfs(root.children[c - 'a'], board, i + 1, j, result);
40+
dfs(root.children[tmp - 'a'], board, i + 1, j, result);
4141
}
4242
if (j + 1 < board[0].length) {
43-
dfs(root.children[c - 'a'], board, i, j + 1, result);
43+
dfs(root.children[tmp - 'a'], board, i, j + 1, result);
4444
}
4545

46-
board[i][j] = c;
46+
//backtracking
47+
board[i][j] = tmp;
4748
}
4849

4950
private TrieNode root;
@@ -72,8 +73,7 @@ private TrieNode buildTrie(String[] words) {
7273

7374
public static class Solution2 {
7475
public List<String> findWords(char[][] board, String[] words) {
75-
76-
List<String> result = new ArrayList();
76+
List<String> result;
7777
HashSet<String> set = new HashSet();
7878
for (String word : words) {
7979
for (int i = 0; i < board.length; i++) {
@@ -88,22 +88,22 @@ public List<String> findWords(char[][] board, String[] words) {
8888
return result;
8989
}
9090

91-
private boolean search(char[][] board, int i, int j, int count, String word) {
92-
if (count == word.length()) {
91+
private boolean search(char[][] board, int i, int j, int index, String word) {
92+
if (index == word.length()) {
9393
return true;
9494
}
9595

96-
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(count)) {
96+
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
9797
return false;
9898
}
9999

100100
char temp = board[i][j];
101101
board[i][j] = ' ';
102102

103-
boolean foundWord = search(board, i + 1, j, count + 1, word)
104-
|| search(board, i - 1, j, count + 1, word)
105-
|| search(board, i, j + 1, count + 1, word)
106-
|| search(board, i, j - 1, count + 1, word);
103+
boolean foundWord = search(board, i + 1, j, index + 1, word)
104+
|| search(board, i - 1, j, index + 1, word)
105+
|| search(board, i, j + 1, index + 1, word)
106+
|| search(board, i, j - 1, index + 1, word);
107107
board[i][j] = temp;
108108
return foundWord;
109109
}

‎src/test/java/com/fishercoder/_212Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._212;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import java.util.Arrays;
9+
10+
import static org.junit.Assert.assertEquals;
11+
12+
public class _212Test {
13+
private static _212.Solution1 solution1;
14+
private static _212.Solution2 solution2;
15+
16+
@BeforeClass
17+
public static void setup() {
18+
solution1 = new _212.Solution1();
19+
solution2 = new _212.Solution2();
20+
}
21+
22+
@Test
23+
public void test1() {
24+
assertEquals(Arrays.asList("oa", "oaa"), solution1.findWords(CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray
25+
("[\"o\",\"a\",\"b\",\"n\"],[\"o\",\"t\",\"a\",\"e\"],[\"a\",\"h\",\"k\",\"r\"],[\"a\",\"f\",\"l\",\"v\"]"),
26+
new String[]{"oa", "oaa"}));
27+
assertEquals(Arrays.asList("oa", "oaa"), solution2.findWords(CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray
28+
("[\"o\",\"a\",\"b\",\"n\"],[\"o\",\"t\",\"a\",\"e\"],[\"a\",\"h\",\"k\",\"r\"],[\"a\",\"f\",\"l\",\"v\"]"),
29+
new String[]{"oa", "oaa"}));
30+
}
31+
32+
@Test
33+
public void test2() {
34+
assertEquals(Arrays.asList("oath", "eat"), solution1.findWords(CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray
35+
("[\"o\",\"a\",\"a\",\"n\"],[\"e\",\"t\",\"a\",\"e\"],[\"i\",\"h\",\"k\",\"r\"],[\"i\",\"f\",\"l\",\"v\"]"),
36+
new String[]{"oath", "pea", "eat", "rain"}));
37+
assertEquals(Arrays.asList("oath", "eat"), solution2.findWords(CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray
38+
("[\"o\",\"a\",\"a\",\"n\"],[\"e\",\"t\",\"a\",\"e\"],[\"i\",\"h\",\"k\",\"r\"],[\"i\",\"f\",\"l\",\"v\"]"),
39+
new String[]{"oath", "pea", "eat", "rain"}));
40+
}
41+
42+
}

0 commit comments

Comments
 (0)