✱✱✱ 79. Word Search Leetcode Problem Solution

In this problem we use the concept of backtracking, whenver we find a character matching the first character of our word we check the solution there if it is possible, for that we make four choices as we can move in four diretions left, right , upside and down and backtrack if we don’t find the solution while traversing one of our possible paths.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution:
    
    def check_word(self,board,word,r,c):
        
        if word[0] == board[r][c] and board[r][c] is not None:
            char_is = board[r][c]
            board[r][c] = None
            word = word[1:]
            if len(word) == 0:
                return True
            
            if (r+1 < len(board) and self.check_word(board,word,r+1,c) ):
                return True
            if (c+1 < len(board[0]) and self.check_word(board,word,r,c+1)):
                return True
            if r-1 > -1 and self.check_word(board,word,r-1,c):
                return True
            if c-1 > -1 and self.check_word(board,word,r,c-1):
                return True

            board[r][c] = char_is
            
        return False
        
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        rows = len(board)
        if rows>0:
            cols= len(board[0])
        
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == word[0]:
                    word_exists = self.check_word(board,word,r,c)
                    if word_exists:
                        return True
        return False
        
        