add a solution for 79

fishercoder1534 · fishercoder1534 · commit 4cc5d27e31fe · 2021-10-07T11:33:07.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_79.java b/src/main/java/com/fishercoder/solutions/_79.java
@@ -44,7 +44,6 @@ boolean search(char[][] board, String word, int i, int j, int pos) {
     // O(1) space solution
     public static class Solution2 {
         public boolean exist(char[][] board, String word) {
-
             // do DFS traversal
             int row = board.length;
             int col = board[0].length;
@@ -64,7 +63,7 @@ private boolean search(char[][] board, int i, int j, String word, int index) {
                 return true;
             }
 
-            // store the visited char in temp variable
+            // store the visited char in a temp variable
             char temp = board[i][j];
             board[i][j] = ' ';
             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) {
             return false;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * I came up with below solution completely independelty on 10/7/2021, although space complexity is O(m*n) instead of constant.
+         */
+        public boolean exist(char[][] board, String word) {
+            int m = board.length;
+            int n = board[0].length;
+            boolean[][] visited = new boolean[m][n];
+            for (int i = 0; i < m; i++) {
+                for (int j = 0; j < n; j++) {
+                    if (board[i][j] == word.charAt(0)) {
+                        visited[i][j] = true;
+                        if (existByDfs(board, i, j, word.substring(1), visited, m, n)) {
+                            return true;
+                        }
+                        //backtracking
+                        visited[i][j] = false;
+                    }
+                }
+            }
+            return false;
+        }
+
+        int[] directions = new int[]{0, 1, 0, -1, 0};
+
+        private boolean existByDfs(char[][] board, int startI, int startJ, String word, boolean[][] visited, int m, int n) {
+            if (word.equals("")) {
+                return true;
+            }
+            for (int i = 0; i < directions.length - 1; i++) {
+                int nextX = startI + directions[i];
+                int nextY = startJ + directions[i + 1];
+                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY] && board[nextX][nextY] == word.charAt(0)) {
+                    visited[nextX][nextY] = true;
+                    if (existByDfs(board, nextX, nextY, word.substring(1), visited, m, n)) {
+                        return true;
+                    }
+                    //backtracking
+                    visited[nextX][nextY] = false;
+                }
+            }
+            return false;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_79Test.java b/src/test/java/com/fishercoder/_79Test.java
@@ -1,5 +1,6 @@
 package com.fishercoder;
 
+import com.fishercoder.common.utils.CommonUtils;
 import com.fishercoder.solutions._79;
 import org.junit.BeforeClass;
 import org.junit.Test;
@@ -9,13 +10,14 @@
 public class _79Test {
     private static _79.Solution1 solution1;
     private static _79.Solution2 solution2;
+    private static _79.Solution3 solution3;
     private static char[][] board;
 
     @BeforeClass
     public static void setup() {
-
         solution1 = new _79.Solution1();
         solution2 = new _79.Solution2();
+        solution3 = new _79.Solution3();
     }
 
     @Test
@@ -61,4 +63,10 @@ public void test4() {
         assertEquals(true, solution2.exist(board, "ABHISHEK"));
     }
 
+    @Test
+    public void test5() {
+        board = CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray("[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]");
+        assertEquals(true, solution3.exist(board, "ABCCED"));
+    }
+
 }
