Jan 25, 2021 · Jan 25, 2021
diff --git a/src/main/java/com/fishercoder/solutions/_79.java b/src/main/java/com/fishercoder/solutions/_79.java
            return false;
        }
    }

    // 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;

            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (board[i][j] == word.charAt(0) && search(board, i, j, word, 0) == true)
                        return true;
                }
            }
            return false;
        }

        private boolean search(char[][] board, int i, int j, String word, int index) {
            if (index == word.length() - 1)
                return true;

            // store the visited char in 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)
                return true;
            if (i < board.length - 1 && board[i + 1][j] == word.charAt(index + 1) && search(board, i + 1, j, word, index + 1) == true)
                return true;

            if (j > 0 && board[i][j - 1] == word.charAt(index + 1) && search(board, i, j - 1, word, index + 1) == true)
                return true;


            if (j < board[0].length - 1 && board[i][j + 1] == word.charAt(index + 1) && search(board, i, j + 1, word, index + 1) == true)
                return true;

            board[i][j] = temp;
            return false;
        }
    }
 }
diff --git a/src/test/java/com/fishercoder/_79Test.java b/src/test/java/com/fishercoder/_79Test.java

 public class _79Test {
    private static _79.Solution1 solution1;
    private static _79.Solution2 solution2;
    private static char[][] board;

    @BeforeClass
    public static void setup() {

        solution1 = new _79.Solution1();
        solution2 = new _79.Solution2();
    }

    @Test
        assertEquals(false, solution1.exist(board, "aaa"));
    }

    @Test
    public void test4() {
        board = new char[][]{
                {'A', 'B', 'H', 'I'},
                {'K', 'E', 'H', 'S'},
                {'A', 'D', 'E', 'E'},
        };
        assertEquals(true, solution2.exist(board, "ABHISHEK"));
    }

 }
Original file line number	Diff line number	Diff line change
Expand Up		@@ -40,4 +40,45 @@ boolean search(char[][] board, String word, int i, int j, int pos) {
		return false;
		}
		}

		// 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;

		for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
		if (board[i][j] == word.charAt(0) && search(board, i, j, word, 0) == true)
		return true;
		}
		}
		return false;
		}

		private boolean search(char[][] board, int i, int j, String word, int index) {
		if (index == word.length() - 1)
		return true;

		// store the visited char in 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)
		return true;
		if (i < board.length - 1 && board[i + 1][j] == word.charAt(index + 1) && search(board, i + 1, j, word, index + 1) == true)
		return true;

		if (j > 0 && board[i][j - 1] == word.charAt(index + 1) && search(board, i, j - 1, word, index + 1) == true)
		return true;


		if (j < board[0].length - 1 && board[i][j + 1] == word.charAt(index + 1) && search(board, i, j + 1, word, index + 1) == true)
		return true;

		board[i][j] = temp;
		return false;
		}
		}
		}
Original file line number	Diff line number	Diff line change
Expand Up		@@ -8,11 +8,14 @@

		public class _79Test {
		private static _79.Solution1 solution1;
		private static _79.Solution2 solution2;
		private static char[][] board;

		@BeforeClass
		public static void setup() {

		solution1 = new _79.Solution1();
		solution2 = new _79.Solution2();
		}

		@Test
Expand DownExpand Up		@@ -48,4 +51,14 @@ public void test3() {
		assertEquals(false, solution1.exist(board, "aaa"));
		}

		@Test
		public void test4() {
		board = new char[][]{
		{'A', 'B', 'H', 'I'},
		{'K', 'E', 'H', 'S'},
		{'A', 'D', 'E', 'E'},
		};
		assertEquals(true, solution2.exist(board, "ABHISHEK"));
		}

		}