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

Commit4cc5d27

Browse files
add a solution for 79
1 parentbbf6254 commit4cc5d27

File tree

2 files changed

+55
-3
lines changed

2 files changed

+55
-3
lines changed

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

Lines changed: 46 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,6 @@ boolean search(char[][] board, String word, int i, int j, int pos) {
4444
// O(1) space solution
4545
publicstaticclassSolution2 {
4646
publicbooleanexist(char[][]board,Stringword) {
47-
4847
// do DFS traversal
4948
introw =board.length;
5049
intcol =board[0].length;
@@ -64,7 +63,7 @@ private boolean search(char[][] board, int i, int j, String word, int index) {
6463
returntrue;
6564
}
6665

67-
// store the visited char in temp variable
66+
// store the visited char inatemp variable
6867
chartemp =board[i][j];
6968
board[i][j] =' ';
7069
if (i >0 &&board[i -1][j] ==word.charAt(index +1) &&search(board,i -1,j,word,index +1) ==true) {
@@ -86,4 +85,49 @@ private boolean search(char[][] board, int i, int j, String word, int index) {
8685
returnfalse;
8786
}
8887
}
88+
89+
publicstaticclassSolution3 {
90+
/**
91+
* I came up with below solution completely independelty on 10/7/2021, although space complexity is O(m*n) instead of constant.
92+
*/
93+
publicbooleanexist(char[][]board,Stringword) {
94+
intm =board.length;
95+
intn =board[0].length;
96+
boolean[][]visited =newboolean[m][n];
97+
for (inti =0;i <m;i++) {
98+
for (intj =0;j <n;j++) {
99+
if (board[i][j] ==word.charAt(0)) {
100+
visited[i][j] =true;
101+
if (existByDfs(board,i,j,word.substring(1),visited,m,n)) {
102+
returntrue;
103+
}
104+
//backtracking
105+
visited[i][j] =false;
106+
}
107+
}
108+
}
109+
returnfalse;
110+
}
111+
112+
int[]directions =newint[]{0,1,0, -1,0};
113+
114+
privatebooleanexistByDfs(char[][]board,intstartI,intstartJ,Stringword,boolean[][]visited,intm,intn) {
115+
if (word.equals("")) {
116+
returntrue;
117+
}
118+
for (inti =0;i <directions.length -1;i++) {
119+
intnextX =startI +directions[i];
120+
intnextY =startJ +directions[i +1];
121+
if (nextX >=0 &&nextX <m &&nextY >=0 &&nextY <n && !visited[nextX][nextY] &&board[nextX][nextY] ==word.charAt(0)) {
122+
visited[nextX][nextY] =true;
123+
if (existByDfs(board,nextX,nextY,word.substring(1),visited,m,n)) {
124+
returntrue;
125+
}
126+
//backtracking
127+
visited[nextX][nextY] =false;
128+
}
129+
}
130+
returnfalse;
131+
}
132+
}
89133
}

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

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
packagecom.fishercoder;
22

3+
importcom.fishercoder.common.utils.CommonUtils;
34
importcom.fishercoder.solutions._79;
45
importorg.junit.BeforeClass;
56
importorg.junit.Test;
@@ -9,13 +10,14 @@
910
publicclass_79Test {
1011
privatestatic_79.Solution1solution1;
1112
privatestatic_79.Solution2solution2;
13+
privatestatic_79.Solution3solution3;
1214
privatestaticchar[][]board;
1315

1416
@BeforeClass
1517
publicstaticvoidsetup() {
16-
1718
solution1 =new_79.Solution1();
1819
solution2 =new_79.Solution2();
20+
solution3 =new_79.Solution3();
1921
}
2022

2123
@Test
@@ -61,4 +63,10 @@ public void test4() {
6163
assertEquals(true,solution2.exist(board,"ABHISHEK"));
6264
}
6365

66+
@Test
67+
publicvoidtest5() {
68+
board =CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray("[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]");
69+
assertEquals(true,solution3.exist(board,"ABCCED"));
70+
}
71+
6472
}

0 commit comments

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