Mercurial

comparison grok_interview/tries.py @ 60:d64a8c189a77

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged
author June Park <me@mrjunejune.com>
date Sat, 20 Dec 2025 13:56:01 -0500
parents 68fa88ac73fe
children
comparison
equal deleted inserted replaced
50:983769fba767 60:d64a8c189a77
1 # Question: Alphabet Word Search II
2 #
3 # You are given an M x N board of characters and a list of strings called dictionary. Find all unique words in the dictionary that can be found in the board.
4 #
5 # A word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally, vertically, or diagonally neighboring. The same letter cell may not be used more than once in a single word.
6 #
7 # Implement a function findWords(board, dictionary) that returns a list of all unique words found.
8 #
9 # Example:
10 #
11 # Board:
12 #
13 # [['o', 'a', 'b', 'n'],
14 # ['o', 't', 'a', 'e'],
15 # ['a', 'h', 'k', 'r'],
16 # ['a', 'f', 'l', 'v']]
17 #
18
19 # Dictionary: ["oath", "pea", "eat", "rain", "hobo", "oats"]
20 #
21 # Expected Output: ["oath", "eat", "hobo", "oats"]
22 #
23 # Constraints & Requirements:
24
25 # The search should be optimized for large dictionaries.
26
27 # Clearly explain your chosen data structure and algorithm for prefix matching and path finding.
28
29 from collections import deque
30 from os import wait
31 from typing import List
32
33
34 board = [
35 ['o', 'a', 'b', 'n'],
36 ['o', 't', 'a', 'e'],
37 ['a', 'h', 'k', 'r'],
38 ['a', 'f', 'l', 'v']
39 ]
40 dictionary = ["oath", "pea", "eat", "rain", "hobo", "oats"]
41 directions = [
42 (0, 1),
43 (0, -1),
44 (1, 0),
45 (-1, 0),
46 (1, 1),
47 (-1, -1),
48 (1, -1),
49 (-1, 1),
50 ]
51
52 def find_words(board: List[List[str]], dictionary: List[str]):
53 tree = {}
54 for row in range(len(board)):
55 for col in range(len(board)):
56 dfs(row, col, tree)
57
58 ans = []
59 for word in dictionary:
60 curr = tree
61 possible = True
62 for letter in word:
63 if letter not in curr:
64 possible = False
65 break
66 curr = curr[letter]
67 if possible:
68 ans.append(word)
69
70 return ans
71
72
73 def dfs(row, col, tree):
74 if not (row >= 0 and row < len(board)\
75 and col >= 0 and col < len(board[0])):
76 return {}
77
78 if board[row][col] == "#":
79 return {}
80
81 letter = board[row][col]
82 children = {}
83 board[row][col] = "#"
84
85 for direction in directions:
86 new_row, new_col = row + direction[0], col + direction[1]
87 child_node = dfs(new_row, new_col, tree[letter])
88 if child_node:
89 children.update(child_node)
90
91 board[row][col] = letter
92
93 return { letter: children }
94
95 print(find_words(board, dictionary))