Update Word Search.java

varunu28 · web-flow · commit 99ca85102e36 · 2021-10-07T08:35:21.000-05:00
diff --git a/Medium/Word Search.java b/Medium/Word Search.java
@@ -2,32 +2,33 @@ class Solution {
   public static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
   
   public boolean exist(char[][] board, String word) {
-    int rows = board.length;
-    int cols = board[0].length;
+    char[] letters = word.toCharArray();
     for (int i = 0; i < board.length; i++) {
       for (int j = 0; j < board[0].length; j++) {
-        if (dfs(board, word, 0, new boolean[rows][cols], i, j)) {
+        if (dfs(board, 0, letters, i, j)) {
           return true;
         }
       }
     }
     return false;
   }
 
-  private boolean dfs(char[][] board, String word, int idx, boolean[][] visited, int i, int j) {
-    if (idx == word.length()) {
+  private boolean dfs(char[][] board, int idx, char[] letters, int i, int j) {
+    if (idx == letters.length) {
       return true;
     }
-    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]
-        || board[i][j] != word.charAt(idx)) {
+    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
       return false;
     }
-    visited[i][j] = true;
-    boolean ans = false;
+    if (board[i][j] != letters[idx]) {
+      return false;
+    }
+    board[i][j] ^= 256;
+    boolean exists = false;
     for (int[] dir : DIRS) {
-      ans = ans || dfs(board, word, idx + 1, visited, i + dir[0], j + dir[1]);
+      exists = exists || dfs(board, idx + 1, letters, i + dir[0], j + dir[1]);
     }
-    visited[i][j] = false;
-    return ans;
+    board[i][j] ^= 256;
+    return exists;
   }
 }

Original file line number	Diff line number	Diff line change
`@@ -2,32 +2,33 @@ class Solution {`
`2`	`2`	`public static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};`
`3`	`3`
`4`	`4`	`public boolean exist(char[][] board, String word) {`
`5`		`- int rows = board.length;`
`6`		`- int cols = board[0].length;`
	`5`	`+ char[] letters = word.toCharArray();`
`7`	`6`	`for (int i = 0; i < board.length; i++) {`
`8`	`7`	`for (int j = 0; j < board[0].length; j++) {`
`9`		`- if (dfs(board, word, 0, new boolean[rows][cols], i, j)) {`
	`8`	`+ if (dfs(board, 0, letters, i, j)) {`
`10`	`9`	`return true;`
`11`	`10`	`}`
`12`	`11`	`}`
`13`	`12`	`}`
`14`	`13`	`return false;`
`15`	`14`	`}`
`16`	`15`
`17`		`- private boolean dfs(char[][] board, String word, int idx, boolean[][] visited, int i, int j) {`
`18`		`- if (idx == word.length()) {`
	`16`	`+ private boolean dfs(char[][] board, int idx, char[] letters, int i, int j) {`
	`17`	`+ if (idx == letters.length) {`
`19`	`18`	`return true;`
`20`	`19`	`}`
`21`		`- if (i < 0 \|\| i >= board.length \|\| j < 0 \|\| j >= board[0].length \|\| visited[i][j]`
`22`		`- \|\| board[i][j] != word.charAt(idx)) {`
	`20`	`+ if (i < 0 \|\| i >= board.length \|\| j < 0 \|\| j >= board[0].length) {`
`23`	`21`	`return false;`
`24`	`22`	`}`
`25`		`- visited[i][j] = true;`
`26`		`- boolean ans = false;`
	`23`	`+ if (board[i][j] != letters[idx]) {`
	`24`	`+ return false;`
	`25`	`+ }`
	`26`	`+ board[i][j] ^= 256;`
	`27`	`+ boolean exists = false;`
`27`	`28`	`for (int[] dir : DIRS) {`
`28`		`- ans = ans \|\| dfs(board, word, idx + 1, visited, i + dir[0], j + dir[1]);`
	`29`	`+ exists = exists \|\| dfs(board, idx + 1, letters, i + dir[0], j + dir[1]);`
`29`	`30`	`}`
`30`		`- visited[i][j] = false;`
`31`		`- return ans;`
	`31`	`+ board[i][j] ^= 256;`
	`32`	`+ return exists;`
`32`	`33`	`}`
`33`	`34`	`}`