Leetcode Problem 79 Word Search.txt

79. Word Search
Given a 2D board and a word, find if the word exists in the grid.

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

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.


Hint to solve: Perform DFS on the cell which matches the first character of the word.
Also store the value of cell into a temp variable. 
Perform DFS recrusive call.
Reset the cell value from temp.
Return the result.



class Solution:
    
    def DFS(self, board:List[List[str]], word: str, wordIndex: int, row: int, col: int) -> bool:
        
        if(wordIndex == len(word)):
            return True
        
        if(row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[wordIndex]):
            return False
        
        wordIndex += 1
        temp = board[row][col]
        board[row][col] = '-'
        
        result = (self.DFS(board, word, wordIndex, row - 1, col) or self.DFS(board, word, wordIndex, row + 1, col) 
                  or self.DFS(board, word, wordIndex, row, col+1) or self.DFS(board, word, wordIndex, row, col-1))

        board[row][col] = temp
        
        return result
        
        
    
    def exist(self, board: List[List[str]], word: str) -> bool:
        for row in range(len(board)):
            for col in range(len(board[0])):
                if(board[row][col] == word[0] and self.DFS(board, word, 0, row, col)):
                    return True
                
        return False