Created
October 22, 2020 03:26
-
-
Save Levi-Lesches/5056b0b07f3c48a283e635621522bd00 to your computer and use it in GitHub Desktop.
LeetCode word search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
# Allows us to do "for coordinate in self" | |
def __iter__(self): return ( | |
(row, column) | |
for row in range(self.rows) | |
for column in range(self.columns) | |
) | |
# Allows us to do "self [coordinate]" | |
def __getitem__(self, coordinate): return self.board [coordinate [0]] [coordinate [1]] | |
# Detects if an answer exists. Returns true or false | |
def exist(self, board, word) -> bool: | |
self.board = board | |
self.target = word | |
self.rows = len(board) | |
self.columns = len(board [0]) | |
self.length = len(word) - 1 | |
if (self.rows * self.columns) < len(word): return False | |
for coordinate in self.search_for_letter(word [0]): | |
if self [coordinate] == self.target: return True | |
if self.recurse(1, coordinate, visited = {coordinate}): | |
return True | |
else: | |
return False | |
# Tries to find the letter at "index" from "coordinate" | |
# "visited" is the set of all visited coordinates, so it can't go back | |
def recurse(self, index, coordinate, visited = set()): | |
# print(f"Trying to find {self.target [index]} from {coordinate} with {visited}") | |
for neighbor in self.get_neighbors(coordinate): | |
if self [neighbor] == self.target [index] and neighbor not in visited: | |
# print(f"Visiting {self.target [index]} at {neighbor}") | |
# print(f" Already visited: {visited}") | |
if ( | |
index == self.length | |
or self.recurse(index + 1, neighbor, visited.union({neighbor})) | |
): | |
# print(f"THIS IS IT. FOUND {self.target [index]} at {neighbor}") | |
return True | |
else: | |
# print(f"Could not find {self.target [index]} from {coordinate}") | |
return False | |
# Returns the coordinate for a given letter. May return more than one. | |
def search_for_letter(self, target_letter): return ( | |
coordinate | |
for coordinate in self | |
if self [coordinate] == target_letter | |
) | |
# Gets all (valid) neighbors for a given coordinate | |
def get_neighbors(self, coordinate): | |
result = [] | |
if (coordinate [0] != 0): | |
result.append( (coordinate [0] - 1, coordinate [1]) ) | |
if coordinate [0] != self.rows - 1: | |
result.append( (coordinate [0] + 1, coordinate [1]) ) | |
if coordinate [1] != 0: | |
result.append( (coordinate [0], coordinate [1] - 1) ) | |
if coordinate [1] != self.columns - 1: | |
result.append( (coordinate [0], coordinate [1] + 1) ) | |
return result | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment