# 79\. Word Search

"""
backtracking
step 1: if not match or if out-of-bound, return False
step 2: add to seen
step 3: take OR among: up, down, left, right
step 4: remove from seen

PS: early stop

time: O(N * 3^L)
N = m*n 
L = len(word)
space: recursion stack: O(L)
"""
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) == 0 or len(board[0]) == 0:
            return False
        
        m = len(board)
        n = len(board[0])
        
        def inside(i, j):
            return 0 <= i < m and 0 <= j < n
        
        def backtrack(target_word, i, j, visited):
            if len(target_word) == 0:
                return True
            if (i, j) in visited:
                return False
            if not inside(i, j) or target_word[0] != board[i][j]:
                return False
            
            visited.add((i, j))
            # try to check here, guarantee backtrack() receive only inbound/unseen i,j
            up = backtrack(target_word[1:], i - 1, j, visited)
            down = backtrack(target_word[1:], i + 1, j, visited)
            left = backtrack(target_word[1:], i, j - 1, visited)
            right = backtrack(target_word[1:], i, j + 1, visited)
            # early stop
            visited.remove((i, j))
            
            return up or down or left or right  # Don't need to know all four results
            
        for i, row in enumerate(board):
            for j, ch in enumerate(row):
                visited = set()
                if backtrack(word, i, j, visited):
                    return True
        return False
    
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) == 0 or len(board[0]) == 0:
            return False
        
        m = len(board)
        n = len(board[0])
        len_word = len(word)
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def inside(i, j):
            return 0 <= i < m and 0 <= j < n

        def is_matched(k, i, j, visited):
            # guaranteed i,j to be inbound
            
            if board[i][j] != word[k]:
                return False
            if k == len_word - 1:  # ch is match and it's the last one
                return True
            
            visited.add((i, j))
            for di, dj in directions:
                newi, newj = i + di, j + dj
                if inside(newi, newj) and (newi, newj) not in visited:
                    if is_matched(k + 1, newi, newj, visited):
                        return True  # early stop
            visited.remove((i, j))
            return False
        
        visited = set()
        for i, row in enumerate(board):
            for j, ch in enumerate(row):
                if is_matched(0, i, j, visited):
                    return True
        return False