Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd416d34

Browse files
refactor 212
1 parent3dd8ae4 commitd416d34

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
privatevoiddfs(TrieNoderoot,char[][]board,inti,intj,List<String>result) {
22-
charc =board[i][j];
22+
chartmp =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
privateTrieNoderoot;
@@ -72,8 +73,7 @@ private TrieNode buildTrie(String[] words) {
7273

7374
publicstaticclassSolution2 {
7475
publicList<String>findWords(char[][]board,String[]words) {
75-
76-
List<String>result =newArrayList();
76+
List<String>result;
7777
HashSet<String>set =newHashSet();
7878
for (Stringword :words) {
7979
for (inti =0;i <board.length;i++) {
@@ -88,22 +88,22 @@ public List<String> findWords(char[][] board, String[] words) {
8888
returnresult;
8989
}
9090

91-
privatebooleansearch(char[][]board,inti,intj,intcount,Stringword) {
92-
if (count ==word.length()) {
91+
privatebooleansearch(char[][]board,inti,intj,intindex,Stringword) {
92+
if (index ==word.length()) {
9393
returntrue;
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
returnfalse;
9898
}
9999

100100
chartemp =board[i][j];
101101
board[i][j] =' ';
102102

103-
booleanfoundWord =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+
booleanfoundWord =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
returnfoundWord;
109109
}
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.common.utils.CommonUtils;
4+
importcom.fishercoder.solutions._212;
5+
importorg.junit.BeforeClass;
6+
importorg.junit.Test;
7+
8+
importjava.util.Arrays;
9+
10+
importstaticorg.junit.Assert.assertEquals;
11+
12+
publicclass_212Test {
13+
privatestatic_212.Solution1solution1;
14+
privatestatic_212.Solution2solution2;
15+
16+
@BeforeClass
17+
publicstaticvoidsetup() {
18+
solution1 =new_212.Solution1();
19+
solution2 =new_212.Solution2();
20+
}
21+
22+
@Test
23+
publicvoidtest1() {
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+
newString[]{"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+
newString[]{"oa","oaa"}));
30+
}
31+
32+
@Test
33+
publicvoidtest2() {
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+
newString[]{"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+
newString[]{"oath","pea","eat","rain"}));
40+
}
41+
42+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp