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]);
        Set<String> newSet = new HashSet<>(set);
        newSet.add(key);
        // left
        boolean a = exist(board, word, maxRow, maxCol, newSet, idx + 1, row, col - 1);
        // up
        boolean b = exist(board, word, maxRow, maxCol, newSet, idx + 1, row - 1, col);
        // right
        boolean c = exist(board, word, maxRow, maxCol, newSet, idx + 1, row, col + 1);
        // down
        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")); // false
    }
}

@@ -217,16 +217,20 @@
 int 
-i
+row
  = 0; 
-i
+row
  %3C b
@@ -242,17 +242,19 @@
 length; 
-i
+row
 ++) %7B%0A  
@@ -276,16 +276,20 @@
 int 
-j
+col
  = 0; 
-j
+col
  %3C b
@@ -289,25 +289,27 @@
 col %3C board%5B
-i
+row
 %5D.length; j+
@@ -306,17 +306,19 @@
 length; 
-j
+col
 ++) %7B%0A  
@@ -363,88 +363,20 @@
 ard%5B
-i%5D%5Bj%5D) %7B%0A//                    System.out.println(%22processing %22 + i + %22, %22 + j);
+row%5D%5Bcol%5D) %7B
 %0A   
@@ -502,17 +502,19 @@
 , board%5B
-i
+row
 %5D.length
@@ -551,76 +551,16 @@
  0, 
-i, j);%0A//                    System.out.println(%22  - found=%22 + found
+row, col
 );%0A 
@@ -1382,26 +1382,24 @@
       %7D%0A
-//
         
 System.o
@@ -1394,119 +1394,9 @@
     
-System.out.println(%22  - val=%22 + board%5Brow%5D%5Bcol%5D);%0A        Set%3CString%3E newSet = new HashSet%3C%3E(set);%0A        newS
+s
 et.a
@@ -1467,36 +1467,33 @@
 maxRow, maxCol, 
-newS
+s
 et, idx + 1, row
@@ -1565,36 +1565,33 @@
 maxRow, maxCol, 
-newS
+s
 et, idx + 1, row
@@ -1666,36 +1666,33 @@
 maxRow, maxCol, 
-newS
+s
 et, idx + 1, row
@@ -1778,12 +1778,9 @@
 ol, 
-newS
+s
 et, 
@@ -1803,31 +1803,40 @@
 , col);%0A
-%0A
+ 
        
- return
+boolean result =
  a %7C b %7C
@@ -1851,757 +1851,88 @@
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem79 prob = new Problem79();%0A//        char%5B%5D%5B%5D board = new char%5B%5D%5B%5D%7B%0A//            %7B'A', 'B', 'C', 'E'%7D,%0A//            %7B'S', 'F', 'C', 'S'%7D,%0A//            %7B'A', 'D', 'E', 'E'%7D,%0A//        %7D;%0A//        System.out.println(prob.exist(board, %22ABCCED%22)); // true%0A//        System.out.println(prob.exist(board, %22SEE%22)); // true%0A//        System.out.println(prob.exist(board, %22ABCB%22)); // false%0A%0A        char%5B%5D%5B%5D board = new char%5B%5D%5B%5D%7B%0A            %7B'a', 'a', 'a', 'a'%7D,%0A            %7B'a', 'a', 'a', 'a'%7D,%0A            %7B'a', 'a', 'a', 'a'%7D,%0A            %7B'a', 'a', 'a', 'a'%7D,%0A            %7B'a', 'a', 'a', 'b'%7D,%0A        %7D;%0A        System.out.println(prob.exist(board, %22aaaaaaaaaaaaaaaaaaaa%22)); // false
+if (!result) %7B%0A            set.remove(key);%0A        %7D%0A        return result;
 %0A   

Solve problem 79