@@ -44,7 +44,6 @@ boolean search(char[][] board, String word, int i, int j, int pos) {
4444// O(1) space solution
4545public static class Solution2 {
4646public boolean exist (char [][]board ,String word ) {
47-
4847// do DFS traversal
4948int row =board .length ;
5049int col =board [0 ].length ;
@@ -64,7 +63,7 @@ private boolean search(char[][] board, int i, int j, String word, int index) {
6463return true ;
6564 }
6665
67- // store the visited char in temp variable
66+ // store the visited char ina temp variable
6867char temp =board [i ][j ];
6968board [i ][j ] =' ' ;
7069if (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) {
8685return false ;
8786 }
8887 }
88+
89+ public static class Solution3 {
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+ public boolean exist (char [][]board ,String word ) {
94+ int m =board .length ;
95+ int n =board [0 ].length ;
96+ boolean [][]visited =new boolean [m ][n ];
97+ for (int i =0 ;i <m ;i ++) {
98+ for (int j =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+ return true ;
103+ }
104+ //backtracking
105+ visited [i ][j ] =false ;
106+ }
107+ }
108+ }
109+ return false ;
110+ }
111+
112+ int []directions =new int []{0 ,1 ,0 , -1 ,0 };
113+
114+ private boolean existByDfs (char [][]board ,int startI ,int startJ ,String word ,boolean [][]visited ,int m ,int n ) {
115+ if (word .equals ("" )) {
116+ return true ;
117+ }
118+ for (int i =0 ;i <directions .length -1 ;i ++) {
119+ int nextX =startI +directions [i ];
120+ int nextY =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+ return true ;
125+ }
126+ //backtracking
127+ visited [nextX ][nextY ] =false ;
128+ }
129+ }
130+ return false ;
131+ }
132+ }
89133}