Update Word Search.java

varunu28 · web-flow · commit 563ba954dbc3 · 2022-11-24T07:50:33.000-08:00
diff --git a/Medium/Word Search.java b/Medium/Word Search.java
@@ -1,34 +1,33 @@
 class Solution {
-  
-  private final int[][] DIRS = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
-  
-  public boolean exist(char[][] board, String word) {
-    int m = board.length;
-    int n = board[0].length;
-    for (int i = 0; i < board.length; i++) {
-      for (int j = 0; j < board[0].length; j++) {
-        if (found(board, i, j, word, 0, m, n)) {
-          return true;
+    
+    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
+    
+    public boolean exist(char[][] board, String word) {
+        int m = board.length;
+        int n = board[0].length;
+        for (int i = 0; i < m; i++) {
+            for (int j = 0; j < n; j++) {
+                if (isFound(board, word, 0, i, j, m, n)) {
+                    return true;
+                }
+            }
         }
-      }
+        return false;
     }
-    return false;
-  }
-  
-  private boolean found(char[][] board, int x, int y, String word, int idx, int m, int n) {
-    if (idx == word.length()) {
-      return true;
-    }
-    if (x < 0 || x == m || y < 0 || y == n || board[x][y] != word.charAt(idx)) {
-      return false;
-    }
-    board[x][y] = '#';
-    for (int[] dir : DIRS) {
-      if (found(board, x + dir[0], y + dir[1], word, idx + 1, m, n)) {
-        return true;
-      }
+    
+    private boolean isFound(char[][] board, String word, int idx, int row, int col, int m, int n) {
+        if (idx == word.length()) {
+            return true;
+        }
+        if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != word.charAt(idx)) {
+            return false;
+        }
+        board[row][col] ^= 256;
+        boolean result = false;
+        for (int[] dir : DIRS) {
+            result = result || isFound(board, word, idx + 1, row + dir[0], col + dir[1], m, n);
+        }
+        board[row][col] ^= 256;
+        return result;
     }
-    board[x][y] = word.charAt(idx);
-    return false;
-  }
 }
