package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/word-search/
 */
public class Problem79 {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (word.charAt(0) == board[i][j]) {
//                    System.out.println("processing " + i + ", " + j);
                    Set<String> set = new HashSet<>();
                    boolean found = exist(board, word, board.length, board[i].length,
                        set, 0, i, j);
//                    System.out.println("  - found=" + found);
                    if (found) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean exist(char[][] board, String word, int maxRow, int maxCol,
                          Set<String> set,
                          int idx, int row, int col) {
        String key = row + "|" + col;
        if (col < 0 || col >= maxCol || row < 0 || row >= maxRow) {
            return false;
        }
        if (idx >= word.length()) {
            return false;
        }
        if (board[row][col] != word.charAt(idx)) {
            return false;
        }
        if (set.contains(key)) {
            return false;
        }
        if (board[row][col] == word.charAt(idx) && idx == word.length() - 1) {
            return true;
        }
//        System.out.println("  - val=" + board[row][col]);
        // left
        Set<String> newSet = new HashSet<>(set);
        newSet.add(key);
        boolean a = exist(board, word, maxRow, maxCol, newSet, idx + 1, row, col - 1);
        // up
        newSet = new HashSet<>(set);
        newSet.add(key);
        boolean b = exist(board, word, maxRow, maxCol, newSet, idx + 1, row - 1, col);
        // right
        newSet = new HashSet<>(set);
        newSet.add(key);
        boolean c = exist(board, word, maxRow, maxCol, newSet, idx + 1, row, col + 1);
        // down
        newSet = new HashSet<>(set);
        newSet.add(key);
        boolean d = exist(board, word, maxRow, maxCol, newSet, idx + 1, row + 1, col);

        return a | b | c | d;
    }

    public static void main(String[] args) {
        Problem79 prob = new Problem79();
//        char[][] board = new char[][]{
//            {'A', 'B', 'C', 'E'},
//            {'S', 'F', 'C', 'S'},
//            {'A', 'D', 'E', 'E'},
//        };
//        System.out.println(prob.exist(board, "ABCCED")); // true
//        System.out.println(prob.exist(board, "SEE")); // true
//        System.out.println(prob.exist(board, "ABCB")); // false

        char[][] board = new char[][]{
            {'a', 'a', 'a', 'a'},
            {'a', 'a', 'a', 'a'},
            {'a', 'a', 'a', 'a'},
            {'a', 'a', 'a', 'a'},
            {'a', 'a', 'a', 'b'},
        };
        System.out.println(prob.exist(board, "aaaaaaaaaaaaaaaaaaaa"));
    }
}

@@ -1558,24 +1558,8 @@
 %5D);%0A
-        // left%0A
     
@@ -1595,32 +1595,32 @@
 HashSet%3C%3E(set);%0A
+
         newSet.a
@@ -1620,32 +1620,48 @@
 ewSet.add(key);%0A
+        // left%0A
         boolean 
@@ -1749,70 +1749,8 @@
  up%0A
-        newSet = new HashSet%3C%3E(set);%0A        newSet.add(key);%0A
     
@@ -1853,70 +1853,8 @@
 ght%0A
-        newSet = new HashSet%3C%3E(set);%0A        newSet.add(key);%0A
     
@@ -1932,24 +1932,24 @@
 , col + 1);%0A
+
         // d
@@ -1956,70 +1956,8 @@
 own%0A
-        newSet = new HashSet%3C%3E(set);%0A        newSet.add(key);%0A
     
@@ -2814,16 +2814,25 @@
 aaaa%22));
+ // false
 %0A    %7D%0A%7D

Update problem 79