|
51
|
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))
|
