LC79. Word Search

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
 
        # 3. Keep a set to track letters we saw in the board for each
        # `search` operation
        visited = set()
 
        def search(board, i, j, word):
            # 4. Is word empty, i.e, found all letters? Then yay!
            if len(word) == 0:
                return True
 
            # 5. Is not in bounds? Bail.
            if not (0 <= i < m and 0 <= j < n):
                return False
            
            # 6. Is visited? Bail.
            if (i, j) in visited:
                return False
 
            # 7. Is not matching first letter in word? Bail.
            if board[i][j] != word[0]:
                return False
 
            # 8. Current letter found, slice and find remaining letters
            word = word[1:]
 
            # 9. Add to visited and traverse adjacent nodes
            visited.add((i, j))
            
            if search(board, i + 1, j, word) or \
                   search(board, i - 1, j, word) or \
                   search(board, i, j + 1, word) or \
                   search(board, i, j - 1, word):
                   return True
            
            # 10. Need to remove from visited since for other branches/graph paths, (i, j)
            # might still not be visited
            visited.remove((i, j))
            
            return False
 
        # 0. Early bail conditions
        # 0.1. If word is longer than board, yeet.
        if len(word) > m * n:
            return False
        
        # 0.2. If chars in word > chars in board, yeet (since can't include already visited)
        if Counter(word) > Counter(chain(*board)):
            return False
        
        # 0.3. For cases like "aaaaaaab", it's better to reverse the word and check since we
        # can optimize for the fail cases and bail/find early.
        counts = Counter(word)
        if counts[word[0]] > counts[word[-1]]:
            word = word[::-1]
 
        # 1. Iterate through the board and start finding if we have the first letter
        # of the word
        for i in range(m):
            for j in range(n):
                # 2. If we find first letter, traverse to see if we can get the word
                if word[0] == board[i][j] and search(board, i, j, word):
                    return True
                
                visited = set()
        
        return False

Complexity

Time: $O(N\cdot 3^L)$ where $N$ is number of cells in board and $L$ is length of the word.

LC explanation:

See In worst case we have to travel till last cell of the matrix and now in last cell our recursion depth will go as far $3^L$ , now why not $4^L$ because we never visit the path where we came from, which is the base case. i.e say we found the first letter, and then the second letter. Now, when we traverse, we have 4 possible paths (assume good case), but we will not go back to the first letter again (i.e travel backwards).

Space: $O(L)$ where $L$ is length of the word since this is how the stack would grow.

Notes

Backtracking is costly, figure out ways to bail early.

A way to avoid visited is to manipulate the board and make the squares "" before traversing adjacent nodes and restore the square value after traversal.