Leetcode 79. Word Search

Problem

Leetcode 79 - Word Search

Example:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Approach

We can find the word in the array by running DFS on each element, and using visited array

Here is the Python code for the solution:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]

        def dfs(i, j, word_index):
            if word_index == len(word):
                return True
            if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) 
                or board[i][j] != word[word_index] or visited[i][j]:
                return False
            
            visited[i][j] = True
            res = (dfs(i+1, j, word_index+1) or dfs(i-1, j, word_index+1) or
                dfs(i, j+1, word_index+1) or dfs(i, j-1, word_index+1))
            visited[i][j] = False

            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True

        return False    

Time Complexity and Space Complexity

Time Complexity: $O(m * 4^n)$

Space Complexity: $O(n*m)$