79.-word-search.md

description
DFS

79. Word Search

• Medium

• 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.

Analysis

The solution here uses DFS(Deep first search). It is similar to backtrcking but is used to solve a graph problem（and also about relationships）. For each node in the graph, we randomly choose a node that is connected to it. If the node we chose has been visited (use a list or dic to record that fact), then we back track. Eventually when our code will go through all the connected nodes and eventually back track to the starting point.

{% embed url="https://www.youtube.com/watch?v=TIbUeeksXcI" %}

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n=len(board)
        m=len(board[0])
        for i in range(n):
            for j in range(m):
                if self.dfs(n,m,i,j,word,board):
                    return True
        return False 
    
    def dfs(self,n,m,i,j,word,board):
        if not word:
            return True 
        if i>=n or j>=m or i<0 or j<0 or board[i][j]!=word[0]:
            return False 
        temp=board[i][j]
        board[i][j]="!"
        ans=self.dfs(n,m,i,j-1,word[1:],board) or self.dfs(n,m,i,j+1,word[1:],board) or self.dfs(n,m,i+1,j,word[1:],board) or self.dfs(n,m,i-1,j,word[1:],board)
        board[i][j]=temp
        return ans