word-searchV1.py (2924B)
1 from collections import namedtuple 2 3 # IDEA: 4 5 # Find an instance of the first character 6 # once this has been found, we then define the surrounding area as 7 # a board and we look for all instances of the second character there 8 # we perform this recursively until we have found the entire word 9 # or we end 10 11 # this process can be optimized with memoization by checking if we have been to a given position with a given word prior to that position being entered. 12 13 14 class Solution: 15 def exist(self, board: List[List[str]], word: str) -> bool: 16 17 Position = namedtuple("Position", ["row", "col"]) 18 word = word[::-1] 19 20 for row in range(len(board)): 21 for col in range(len(board[row])): 22 if board[row][col] == word[0]: 23 is_found = backtrack_adjacent( 24 Position(row, col), word[1:], board, Position, set(), set() 25 ) 26 if is_found: 27 return True 28 29 return False 30 31 32 # consider memoization 33 # check if we've been here when the remaining size has been the same. 34 35 36 def backtrack_adjacent( 37 position, word_remaining, board, Position, visited, memo 38 ) -> bool: 39 40 current = str(position.row) + " " + str(position.col) 41 42 if current in visited: 43 return False 44 45 visited.add(current) 46 47 current_mem = current + " " + str(len(word_remaining)) 48 if current_mem in memo: 49 return False 50 51 if not word_remaining: 52 return True 53 54 # left 55 56 if position.row + -1 >= 0: 57 new_pos = Position(-1 + position.row, position.col) 58 if board[new_pos.row][new_pos.col] == word_remaining[0]: 59 res = backtrack_adjacent( 60 new_pos, word_remaining[1:], board, Position, visited.copy(), memo 61 ) 62 if res: 63 return True 64 65 # right 66 67 if position.row + 1 < len(board): 68 new_pos = Position(1 + position.row, position.col) 69 if board[new_pos.row][new_pos.col] == word_remaining[0]: 70 res = backtrack_adjacent( 71 new_pos, word_remaining[1:], board, Position, visited.copy(), memo 72 ) 73 if res: 74 return True 75 # up 76 if position.col + -1 >= 0: 77 new_pos = Position(position.row, -1 + position.col) 78 if board[new_pos.row][new_pos.col] == word_remaining[0]: 79 res = backtrack_adjacent( 80 new_pos, word_remaining[1:], board, Position, visited.copy(), memo 81 ) 82 if res: 83 return True 84 # down 85 if position.col + 1 < len(board[0]): 86 new_pos = Position(position.row, 1 + position.col) 87 if board[new_pos.row][new_pos.col] == word_remaining[0]: 88 res = backtrack_adjacent( 89 new_pos, word_remaining[1:], board, Position, visited.copy(), memo 90 ) 91 if res: 92 return True 93 94 return False