WordSearch.py

# Question link - https://leetcode.com/problems/word-search/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # This problem uses the brute force backtracking problem 
        # Get the dimensions for the board
        ROWS,COLS = len(board),len(board[0])
        # For no duplicate character 
        path = set()

        # Using backtracking function
        # r -> row , c -> col , i -> current character  
        def dfs(r,c,i):
            #Basecase 
            if i == len(word):
                return True
            # Invalid conditions for the word search
            if (r < 0 or c < 0 or 
                r >= ROWS or c >= COLS or
                word[i] != board[r][c] or
                (r,c) in path):
                return False

            # Track the path 
            path.add((r,c))
            res = (dfs(r + 1 , c , i+ 1)or 
                   dfs(r - 1 , c , i + 1)or
                   dfs(r , c + 1 , i + 1)or
                   dfs(r , c - 1 , i + 1))

            # Clean the path 
            path.remove((r,c))
            return res 

        # Traverse the board 
        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r,c,0): return True 

        return False

        # This is not efficient algo - > O(n * m * 4^ n)
        # Brute force algorithm