| 2 | 2 | |
| 3 | 3 | class Point: |
| 4 | 4 | def __init__(self, x: int, y: int) -> None: |
| 5 | | self.x = None |
| 6 | | self.y = None |
| 5 | self.x = x |
| 6 | self.y = y |
| 7 | 7 | |
| 8 | 8 | def __eq__(self, other: object) -> bool: |
| 9 | if not isinstance(other, Point): |
| 10 | return False |
| 9 | 11 | return self.x == other.x and self.y == other.y |
| 10 | 12 | |
| 11 | 13 | |
| 12 | 14 | class WordSearch: |
| 13 | 15 | def __init__(self, puzzle: List[str]) -> None: |
| 14 | | pass |
| 16 | # Edge Case: Empty puzzle |
| 17 | if not puzzle: |
| 18 | self.puzzle = [] |
| 19 | self.height = 0 |
| 20 | self.width = 0 |
| 21 | return |
| 22 | |
| 23 | self.puzzle = puzzle |
| 24 | self.height = len(puzzle) |
| 25 | # Edge Case: Puzzle with irregular dimensions |
| 26 | self.width = len(puzzle[0]) if puzzle else 0 |
| 15 | 27 | |
| 16 | 28 | def search(self, word: str) -> Optional[Tuple[Point, Point]]: |
| 17 | | pass |
| 29 | # Edge Case: Empty word |
| 30 | if not word: |
| 31 | return None |
| 32 | |
| 33 | # Edge Case: Empty puzzle |
| 34 | if not self.puzzle or self.height == 0 or self.width == 0: |
| 35 | return None |
| 36 | |
| 37 | # Define all 8 directions: right, left, down, up, down-right, down-left, up-right, up-left |
| 38 | directions = [ |
| 39 | (0, 1), # right |
| 40 | (0, -1), # left |
| 41 | (1, 0), # down |
| 42 | (-1, 0), # up |
| 43 | (1, 1), # down-right |
| 44 | (1, -1), # down-left |
| 45 | (-1, 1), # up-right |
| 46 | (-1, -1) # up-left |
| 47 | ] |
| 48 | |
| 49 | # Edge Case: Word longer than puzzle dimensions |
| 50 | if len(word) > self.height and len(word) > self.width: |
| 51 | # Check diagonal dimensions too |
| 52 | if len(word) > min(self.height, self.width): |
| 53 | return None |
| 54 | |
| 55 | for y in range(self.height): |
| 56 | for x in range(self.width): |
| 57 | for dy, dx in directions: |
| 58 | # Check if word fits in this direction |
| 59 | end_x = x + (len(word) - 1) * dx |
| 60 | end_y = y + (len(word) - 1) * dy |
| 61 | |
| 62 | # Edge Case: Word goes out of bounds |
| 63 | if end_x < 0 or end_x >= self.width or end_y < 0 or end_y >= self.height: |
| 64 | continue |
| 65 | |
| 66 | # Check if word matches in this direction |
| 67 | found = True |
| 68 | for i in range(len(word)): |
| 69 | curr_x = x + i * dx |
| 70 | curr_y = y + i * dy |
| 71 | if self.puzzle[curr_y][curr_x] != word[i]: |
| 72 | found = False |
| 73 | break |
| 74 | |
| 75 | if found: |
| 76 | # Return start and end points (0-indexed) |
| 77 | return (Point(x, y), Point(end_x, end_y)) |
| 78 | |
| 79 | # Edge Case: Word not found in puzzle |
| 80 | return None |
| 81 | # Handled Edge Cases: Empty word, empty puzzle, puzzle with irregular dimensions, word longer than puzzle dimensions, word goes out of bounds, word not found in puzzle |