Commit04a0f72

authored

added solution and test case for 79 (#150)

1 parent58bdfd2 commit04a0f72Copy full SHA for 04a0f72

File tree

+54

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _79.java
- test/java/com/fishercoder
  - _79Test.java

+54

-0

lines changed

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -40,4 +40,45 @@ boolean search(char[][] board, String word, int i, int j, int pos) {`
`40`	`40`	`returnfalse;`
`41`	`41`	`}`
`42`	`42`	`}`
	`43`	`+`
	`44`	`+// O(1) space solution`
	`45`	`+publicstaticclassSolution2 {`
	`46`	`+publicbooleanexist(char[][]board,Stringword) {`
	`47`	`+`
	`48`	`+// do DFS traversal`
	`49`	`+introw =board.length;`
	`50`	`+intcol =board[0].length;`
	`51`	`+`
	`52`	`+for (inti =0;i <row;i++) {`
	`53`	`+for (intj =0;j <col;j++) {`
	`54`	`+if (board[i][j] ==word.charAt(0) &&search(board,i,j,word,0) ==true)`
	`55`	`+returntrue;`
	`56`	`+ }`
	`57`	`+ }`
	`58`	`+returnfalse;`
	`59`	`+ }`
	`60`	`+`
	`61`	`+privatebooleansearch(char[][]board,inti,intj,Stringword,intindex) {`
	`62`	`+if (index ==word.length() -1)`
	`63`	`+returntrue;`
	`64`	`+`
	`65`	`+// store the visited char in temp variable`
	`66`	`+chartemp =board[i][j];`
	`67`	`+board[i][j] =' ';`
	`68`	`+if (i >0 &&board[i -1][j] ==word.charAt(index +1) &&search(board,i -1,j,word,index +1) ==true)`
	`69`	`+returntrue;`
	`70`	`+if (i <board.length -1 &&board[i +1][j] ==word.charAt(index +1) &&search(board,i +1,j,word,index +1) ==true)`
	`71`	`+returntrue;`
	`72`	`+`
	`73`	`+if (j >0 &&board[i][j -1] ==word.charAt(index +1) &&search(board,i,j -1,word,index +1) ==true)`
	`74`	`+returntrue;`
	`75`	`+`
	`76`	`+`
	`77`	`+if (j <board[0].length -1 &&board[i][j +1] ==word.charAt(index +1) &&search(board,i,j +1,word,index +1) ==true)`
	`78`	`+returntrue;`
	`79`	`+`
	`80`	`+board[i][j] =temp;`
	`81`	`+returnfalse;`
	`82`	`+ }`
	`83`	`+ }`
`43`	`84`	`}`

Lines changed: 13 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,11 +8,14 @@`
`8`	`8`
`9`	`9`	`publicclass_79Test {`
`10`	`10`	`privatestatic_79.Solution1solution1;`
	`11`	`+privatestatic_79.Solution2solution2;`
`11`	`12`	`privatestaticchar[][]board;`
`12`	`13`
`13`	`14`	`@BeforeClass`
`14`	`15`	`publicstaticvoidsetup() {`
	`16`	`+`
`15`	`17`	`solution1 =new_79.Solution1();`
	`18`	`+solution2 =new_79.Solution2();`
`16`	`19`	`}`
`17`	`20`
`18`	`21`	`@Test`
`@@ -48,4 +51,14 @@ public void test3() {`
`48`	`51`	`assertEquals(false,solution1.exist(board,"aaa"));`
`49`	`52`	`}`
`50`	`53`
	`54`	`+@Test`
	`55`	`+publicvoidtest4() {`
	`56`	`+board =newchar[][]{`
	`57`	`+ {'A','B','H','I'},`
	`58`	`+ {'K','E','H','S'},`
	`59`	`+ {'A','D','E','E'},`
	`60`	`+ };`
	`61`	`+assertEquals(true,solution2.exist(board,"ABHISHEK"));`
	`62`	`+ }`
	`63`	`+`
`51`	`64`	`}`

Comments

(0)