Mercurial

comparison async_multi_threads/tries.py @ 69:551d9fc0a2ba

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated wrong names.
author June Park <parkjune1995@gmail.com>
date Thu, 25 Dec 2025 20:07:46 -0800
parents
children
comparison
equal deleted inserted replaced
68:70ca1d99f3fd 69:551d9fc0a2ba
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))