Devin's Blog

Word Search

4 min read

Intuition

  • What tripped me up big time regarding this problem was that I started out trying to be smart. That is to say, I tried to find a solution that didn’t involve starting from the first position of the word I was trying to find each time.
    • This is a pointless and nontrivial optimization since you will have to eventually touch each row and column anyway in the worst case.
    • It may make your average case slightly better, but that’s it.
  • Additionally, I started out with DFS, then thought that my bug was that I had used DFS. No, the bug was that sets are not ordered, so you have to remove the element of the set by picking it. I tried to avoid this since that seems slow, but that is what you have to do.
  • You can optimize the code through pruning. That is, check that there are enough letters in the grid to fill the word, and check that each letter count of the word has enough letters on the grid. This places the runtime from 33% to 93%.

Runtime

  1. DFS Complexity: In the worst-case scenario, the DFS can visit all cells in the grid. For each cell, it makes a constant amount of work plus potentially 4 recursive calls (one for each neighboring cell). However, due to the seen set, each cell will be visited at most once. So, for a single DFS call starting from one cell, the worst-case time complexity is , where and are the dimensions of the board.
  2. Outer Loop: The outer double loop iterates over every cell in the grid as the starting point for the DFS, and there are cells. For each cell, the DFS is invoked.
  • Thus, combining the above points, the worst-case runtime complexity is (, which simplifies to .

Code

Includes Pruning Optimization

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        word_len = len(word)
        if m * n < word_len:
            return False
        prune = Counter()
        for i in range(m):
            for j in range(n):
                prune[board[i][j]] += 1
 
        word_count = Counter()
        for c in word:
            word_count[c] += 1
        for c in word_count:
            if prune[c] < word_count[c]:
                return False
            
 
        def adj(r, c):
            res = []
            for i, j in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
                if 0 <= i < m and 0 <= j < n:
                    res.append((i, j))
            return res
        
        path = set()
        def dfs(r, c, index):
            if index >= word_len:
                return True
            path.add((r, c))
            for i, j in adj(r, c):
                if (i, j) not in path \
                    and board[i][j] == word[index] \
                        and dfs(i, j, index + 1):
                            return True
            path.remove((r, c))
            return False
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0] \
                    and dfs(i, j, 1):
                        return True
 
        return False

DFS w/ Backtracking

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
 
        def is_inbounds(r, c):
            return 0 <= r < m and 0 <= c < n
 
        def adj(r, c):
            return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] # left, right, up, down
 
        visited = set()
        def dfs(r, c, i):
            if i == len(word) - 1 and board[r][c] == word[i]:
                return True
            if board[r][c] != word[i]:
                return False
 
            visited.add((r, c))
            for x, y in adj(r, c):
                if is_inbounds(x, y) and (x, y) not in visited:
                    if dfs(x, y, i + 1) == True:
                        return True
            visited.remove((r, c))
            return False
 
        for r in range(m):
            for c in range(n):
                if board[r][c] == word[0]:
                    if dfs(r, c, 0) == True:
                        return True
        
        return False

Notes

References

https://leetcode.com/problems/word-search/ Attempt to Fix issue of the Set

Graph View

Backlinks