optimised v2: 99% runtime (3 ms), 65% memory (17.88 mb), optimised v1: 98% runtime (424 ms ), 40% memory (17.98 mb). v1 74% runtime (3537 ms), 87% memory (17.8 mb) https://leetcode.com/problems/word-search/

word_search_optimised_v2.py

from collections import Counter


DIRS = [
    (+1, 0),
    (0, +1),
    (-1, 0),
    (0, -1)
]

class Solution:
    '''
    potential optimisation:
    if recursion is "bad" and we want to avoid invoking more function calls,
    we can instead use a stack (list) to do iterative DFS.
    idea is to append the next set of dfs fn arguments into the stack.
    then, we pop from the stack, so the most-recently-added arguments.
    
    another tricky part is keeping track of visited ij entries in the board.
    we can use a set of (i,j) tuples to do this, but we need to attach one set per item in the stack.
    ah, or maybe this is not needed. maybe we can still use the same approach of temporarily overriding ij entries by "#". 
  
    the memory costs of all this might outweigh the recursive approach. it should be compared empirically.  
    '''
    def exist(self, board: List[List[str]], word: str) -> bool:
        len_word = len(word)
        nr = len(board)
        nc = len(board[0])

        # ok this is subsumed by the counter optimisation below. 
        # take care of single letter word so that we can eliminate base cases
        # if len_word == 1 and nr == 1 and nc == 1:
        #     return board[0][0] == word[0]

        # angle of attack 2:
        # build Counter of character frequencies in board. if any character is short, no pt doing any DFS.
        # nice, 424 ms, beats 98% now yay!!
        board_counter = Counter(board[i][j] for i in range(nr) for j in range(nc))
        word_counter = Counter(word)
        for char, counts in word_counter.items():
            if board_counter[char] < counts:
                return False

        # angle of attack 3:
        # start from the "rarer" side of word
        # why? bcos it will have fewer matches in the initial phases, helping to prune DFS searches very early on. 
        # nice!!!! 3 ms, beats 99% hehe
        if board_counter[word[-1]] < board_counter[word[0]]:
            word = word[::-1]

        def dfs(i: int, j: int, char_idx: int):
            # cannot remove this, will fail test cases where len(word) == 1
            # it also fails other test cases
            # ah, this is needed to check first char of word exists in board!
            # FIX: check first char matching in double for-loop before starting any dfs
            # if board[i][j] != word[char_idx]:
            #     return False
            
            # a better base case that trims 1 level of recursion
            # note that this requires checking first char of word matches board[i][j] OUTSIDE of dfs()
            if char_idx == len_word - 1:
                return True

            # mark as used
            orig, board[i][j] = board[i][j], "#"

            # check all 4 directions
            found = False
            for di, dj in DIRS:
                new_i, new_j = i + di, j + dj
                # attack 1: let's try to add more conditions here to limit branching
                # nice! managed to improve runtime from 3537ms (74%) to 3112ms (87%)
                # memory use is 17.7mb (96%)
                if (
                    (new_i >= 0 and new_i < nr) and \
                    (new_j >= 0 and new_j < nc) and \
                    board[new_i][new_j] == word[char_idx + 1]
                ):
                    # we don't need to start a new branch here. we already found the solution
                    if char_idx + 1 == len_word - 1:
                        return True
                    found = dfs(new_i, new_j, char_idx + 1)
                    if found:
                        return True
                
            # rmbr to backtrack by restoring original value of ij-th entry in board
            board[i][j] = orig

            return found
        
        # start a DFS at every position
        for i in range(nr):
            for j in range(nc):
                # only bother with dfs if first char is matching
                # nice, cut runtime further to 2950ms, 91% 
                if board[i][j] == word[0]:
                    found = dfs(i, j, 0)
                    if found:
                        return True
        return False

v1 code with some initial optimizations (trimming recursion depth)

DIRS = [
    (+1, 0),
    (0, +1),
    (-1, 0),
    (0, -1)
]

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        len_word = len(word)
        nr = len(board)
        nc = len(board[0])

        # cache failed attempts
        failed_attempts = set()

        def dfs(i: int, j: int, char_idx: int):
            # base case (FIXED: inferior to base case below)
            # if char_idx == len_word:
            #     return True

            # prune search
            # FIXME: cache is not unique enough. we are wrongly aborting branches we should explore.
            # actually caching is useless since every DFS starts from a different starting point.
            # the "history" of every path is different, and there's no benefit to caching anything 
            # if (i, j, char_idx) in failed_attempts:
            #     return False
            
            # check out of bounds, abort search
            # FIXED: doing out-of-bounds check in the below for-loop is better, trims 1 level of recursion
            # if i < 0 or i >= nr or j < 0 or j >= nc:
            #     return False
            
            if board[i][j] != word[char_idx]:
                # print(f"WORD MISMATCH: at {i=}, {j=}, {char_idx=}, {board[i][j]} vs {word[char_idx]}")
                return False
            
            # a better base case that trims 1 level of recursion
            if char_idx == len_word - 1:
                # print(f"SUCCESS: at {i=}, {j=}, {char_idx=}")
                return True

            # mark as used
            # print(f"WORD MATCH: at {i=}, {j=}, {char_idx=}, {board[i][j]} vs {word[char_idx]}")
            orig, board[i][j] = board[i][j], "#"

            # check all 4 directions
            found = False
            for di, dj in DIRS:
                new_i, new_j = i + di, j + dj
                if (new_i >= 0 and new_i < nr) and (new_j >= 0 and new_j < nc):
                    found = dfs(new_i, new_j, char_idx + 1)
                    if found:
                        break
                
            # rmbr to backtrack by restoring original value of ij-th entry in board
            board[i][j] = orig

            # if not found:
            #     # for pruning searches, FIXME: cache is not unique enough.
            #     # print(f"CACHE ADD: false at {i=}, {j=}, {char_idx=}")
            #     failed_attempts.add((i, j, char_idx))
            return found
        
        # start a DFS at every position
        for i in range(nr):
            for j in range(nc):
        # for i in range(1):
        #     for j in range(1):
                found = dfs(i, j, 0)
                if found:
                    return True
        return False

v2 code with 2 angles of attack

from collections import Counter


DIRS = [
    (+1, 0),
    (0, +1),
    (-1, 0),
    (0, -1)
]

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        len_word = len(word)
        nr = len(board)
        nc = len(board[0])

        # take care of single letter word so that we can eliminate base cases
        if len_word == 1 and nr == 1 and nc == 1:
            return board[0][0] == word[0]

        # angle of attack 2:
        # build Counter of character frequencies in board. if any character is short, no pt doing any DFS.
        # nice, 424 ms, beats 98% now yay!!
        board_counter = Counter(board[i][j] for i in range(nr) for j in range(nc))
        word_counter = Counter(word)
        for char, counts in word_counter.items():
            if board_counter[char] < counts:
                return False

        def dfs(i: int, j: int, char_idx: int):
            # cannot remove this, will fail test cases where len(word) == 1
            # it also fails other test cases
            # ah, this is needed to check first char of word exists in board!
            # FIX: check first char matching in double for-loop before starting any dfs
            # if board[i][j] != word[char_idx]:
            #     return False
            
            # a better base case that trims 1 level of recursion
            # note that this requires checking first char of word matches board[i][j] OUTSIDE of dfs()
            if char_idx == len_word - 1:
                return True

            # mark as used
            orig, board[i][j] = board[i][j], "#"

            # check all 4 directions
            found = False
            for di, dj in DIRS:
                new_i, new_j = i + di, j + dj
                # attack 1: let's try to add more conditions here to limit branching
                # nice! managed to improve runtime from 3537ms (74%) to 3112ms (87%)
                # memory use is 17.7mb (96%)
                if (
                    (new_i >= 0 and new_i < nr) and \
                    (new_j >= 0 and new_j < nc) and \
                    board[new_i][new_j] == word[char_idx + 1]
                ):
                    # we don't need to start a new branch here. we already found the solution
                    if char_idx + 1 == len_word - 1:
                        found = True
                        break
                    found = dfs(new_i, new_j, char_idx + 1)
                    if found:
                        break
                
            # rmbr to backtrack by restoring original value of ij-th entry in board
            board[i][j] = orig

            return found
        
        # start a DFS at every position
        for i in range(nr):
            for j in range(nc):
                # only bother with dfs if first char is matching
                # nice, cut runtime further to 2950ms, 91% 
                if board[i][j] == word[0]:
                    found = dfs(i, j, 0)
                    if found:
                        return True
        return False