79. Word Search

Description:

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

'''
[1] back-tracking - out-place)

idea::
back tracking using visited_flag_matrix

code::
def exist(self, board: List[List[str]], word: str) -> bool:
    for r in range(len(board)):
        for c in range(len(board[0])):
            reader=0
            if board[r][c]==word[reader]:
                visited=[[False for _ in range(len(board[0]))] for _ in range(len(board))]

                if self.dfs(board, visited, r, c, word, reader):
                    return True
    return False

def dfs(self, board, visited, r, c, word, reader):
    if reader==len(word)-1:
        return True

    visited[r][c]=True

    above,below,left,right=False,False,False,False
    if r-1>=0 and visited[r-1][c]==False and board[r-1][c]==word[reader+1]:
        above=self.dfs(board,visited,r-1,c,word,reader+1)
        visited[r-1][c]=False

    if r+1<len(board) and visited[r+1][c]==False and board[r+1][c]==word[reader+1]:
        below=self.dfs(board,visited,r+1,c,word,reader+1)
        visited[r+1][c]=False

    if c-1>=0 and visited[r][c-1]==False and board[r][c-1]==word[reader+1]:
        left=self.dfs(board,visited,r,c-1,word,reader+1)
        visited[r][c-1]=False

    if c+1<len(board[0]) and visited[r][c+1]==False and board[r][c+1]==word[reader+1]:
        right=self.dfs(board,visited,r,c+1,word,reader+1)
        visited[r][c+1]=False

    return above|below|left|right

-T/C: O(m*n)
-S/C: O(m*n) # for function call and visited
'''

'''
[2] back-tracking - in-place - optimization)

idea::
overwrite visited_flag on the board.

code::
(below)

-T/C: O(m*n)
-S/C: O(m*n) # for function call. even if using stack, also need to using additional memory.
'''

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for r in range(len(board)):
            for c in range(len(board[0])):
                reader=0
                if board[r][c]==word[reader]:
                    if self.dfs(board, r, c, word, reader):
                        return True
        return False
                    
    def dfs(self, board, r, c, word, reader):
        if reader==len(word)-1:
            return True
        
        tmp=board[r][c]
        board[r][c]="-" #visited
        
        above,below,left,right=False,False,False,False
        if r-1>=0 and board[r-1][c]!='-' and board[r-1][c]==word[reader+1]:
            above=self.dfs(board,r-1,c,word,reader+1)
        
        if r+1<len(board) and board[r+1][c]!='-' and board[r+1][c]==word[reader+1]:
            below=self.dfs(board,r+1,c,word,reader+1)
        
        if c-1>=0 and board[r][c-1]!='-' and board[r][c-1]==word[reader+1]:
            left=self.dfs(board,r,c-1,word,reader+1)
        
        if c+1<len(board[0]) and board[r][c+1]!='-' and board[r][c+1]==word[reader+1]:
            right=self.dfs(board,r,c+1,word,reader+1)
        
        board[r][c]=tmp
            
        return above|below|left|right