leetcode

commit 7ca8c0c67e3e061650467eef9daab8ca09be43ec
parent 76103453bfd2e332e0aa2a8a06e91ae0eec46686
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 15 Jul 2025 16:00:34 -0500

Completed word search

Diffstat:
A
word-search/word-searchV1.py
 | 
94
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 94 insertions(+), 0 deletions(-)
diff --git a/word-search/word-searchV1.py b/word-search/word-searchV1.py
@@ -0,0 +1,94 @@
+from collections import namedtuple
+
+# IDEA:
+
+# Find an instance of the first character
+# once this has been found, we then define the surrounding area as
+# a board and we look for all instances of the second character there
+# we perform this recursively until we have found the entire word
+# or we end
+
+# 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.
+
+
+class Solution:
+    def exist(self, board: List[List[str]], word: str) -> bool:
+
+        Position = namedtuple("Position", ["row", "col"])
+        word = word[::-1]
+
+        for row in range(len(board)):
+            for col in range(len(board[row])):
+                if board[row][col] == word[0]:
+                    is_found = backtrack_adjacent(
+                        Position(row, col), word[1:], board, Position, set(), set()
+                    )
+                    if is_found:
+                        return True
+
+        return False
+
+
+# consider memoization
+# check if we've been here when the remaining size has been the same.
+
+
+def backtrack_adjacent(
+    position, word_remaining, board, Position, visited, memo
+) -> bool:
+
+    current = str(position.row) + " " + str(position.col)
+
+    if current in visited:
+        return False
+
+    visited.add(current)
+
+    current_mem = current + " " + str(len(word_remaining))
+    if current_mem in memo:
+        return False
+
+    if not word_remaining:
+        return True
+
+    # left
+
+    if position.row + -1 >= 0:
+        new_pos = Position(-1 + position.row, position.col)
+        if board[new_pos.row][new_pos.col] == word_remaining[0]:
+            res = backtrack_adjacent(
+                new_pos, word_remaining[1:], board, Position, visited.copy(), memo
+            )
+            if res:
+                return True
+
+    # right
+
+    if position.row + 1 < len(board):
+        new_pos = Position(1 + position.row, position.col)
+        if board[new_pos.row][new_pos.col] == word_remaining[0]:
+            res = backtrack_adjacent(
+                new_pos, word_remaining[1:], board, Position, visited.copy(), memo
+            )
+            if res:
+                return True
+    # up
+    if position.col + -1 >= 0:
+        new_pos = Position(position.row, -1 + position.col)
+        if board[new_pos.row][new_pos.col] == word_remaining[0]:
+            res = backtrack_adjacent(
+                new_pos, word_remaining[1:], board, Position, visited.copy(), memo
+            )
+            if res:
+                return True
+    # down
+    if position.col + 1 < len(board[0]):
+        new_pos = Position(position.row, 1 + position.col)
+        if board[new_pos.row][new_pos.col] == word_remaining[0]:
+            res = backtrack_adjacent(
+                new_pos, word_remaining[1:], board, Position, visited.copy(), memo
+            )
+            if res:
+                return True
+
+    return False