Backtrack
For each word, we can search if it is in the board with backtracking.
from itertools import product as cartesian
class Solution:
def backtrack(self, word, i, r, c, board, visited) -> bool:
if i == len(word):
return True
char = word[i]
m, n = len(board), len(board[0])
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
r2, c2 = r + dr, c + dc
valid_row, valid_col = (0 <= r2 < m), (0 <= c2 < n)
if not valid_row or not valid_col:
continue
if (r2, c2) in visited:
continue
if board[r2][c2] != char:
continue
visited.add((r2, c2))
if self.backtrack(word, i + 1, r2, c2, board, visited):
return True
visited.remove((r2, c2))
return False
def board_contains(self, word, board, char_map) -> bool:
return any(
self.backtrack(word, 1, r, c, board, {(r, c)})
for r, c in char_map.get(word[0], [])
)
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m, n = len(board), len(board[0])
char_map = {}
for r, c in cartesian(range(m), range(n)):
char = board[r][c]
char_map[char] = char_map.get(char, []) + [(r, c)]
return [word for word in words if self.board_contains(word, board, char_map)]
Trie
We can build a trie out of the words to search, excluding a word if its first char does not appear in the board. While collecting words from the trie, we check against the board to see if taking an edge would be consistent with the board:
- The edge leads to a neighboring cell.
- The cell has not already been visited.
Once we find a word, we delete it, reducing size of the trie by one. If the trie is empty, we exit the backtrack early.
from itertools import product as cartesian
class TrieNode:
def __init__(self):
self.deleted = False
self.end_of_word = False
self.edges = {}
class Trie:
def __init__(self):
self.root = TrieNode()
self.size = 0
def insert(self, word):
u = self.root
for char in word:
if char not in u.edges:
u.edges[char] = TrieNode()
u = u.edges[char]
self.size += (0 if u.end_of_word else 1)
u.end_of_word = True
def __delete(self, u, word, i):
if i == len(word):
self.size -= (1 if u.end_of_word else 0)
u.end_of_word = False
if all(v.deleted for v in u.edges.values()):
u.deleted = True
return u
char = word[i]
u.edges[char] = self.__delete(u.edges[char], word, i+1)
if all(v.deleted for v in u.edges.values()):
u.delete = True
return u
def __backtrack(self, u, curr_cell, char_map, visited, curr_word, words):
def is_neibor(next_cell, curr_cell):
dr, dc = next_cell[0]-curr_cell[0], next_cell[1]-curr_cell[1]
return (dr, dc) in {(-1, 0),(0, 1),(1, 0),(0, -1)}
if self.size == 0:
return
if u.end_of_word:
word = "".join(curr_word)
words.add( word )
self.root = self.__delete(self.root, word, 0)
for v_char, v in u.edges.items():
cells = char_map.get(v_char, set())
not_visited_cells = cells-visited
for cell in [c for c in not_visited_cells if is_neibor(c, curr_cell)]:
visited.add(cell)
curr_word.append(v_char)
self.__backtrack(v, cell, char_map, visited, curr_word, words)
curr_word.pop()
visited.remove(cell)
def pop_words(self, char_map):
words = set()
for u_char, u in self.root.edges.items():
for cell in char_map.get(u_char, set()):
self.__backtrack(u, cell, char_map, {cell}, [u_char], words)
return words
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m, n = len(board), len(board[0])
char_map = {}
for r, c in cartesian(range(m), range(n)):
char = board[r][c]
if char not in char_map:
char_map[char] = set()
char_map[char].add( (r, c) )
trie = Trie()
for word in words:
if not word[0] in char_map:
continue
trie.insert(word)
return list(trie.pop_words(char_map))
Instead, we can start from each cell in the board and explore the board only if allowed by the trie. As words are found, we lazily prune the trie.
from itertools import product as cartesian
class TrieNode:
def __init__(self):
self.end_of_word = False
self.edges = {}
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
u = self.root
for char in word:
if char not in u.edges:
u.edges[char] = TrieNode()
u = u.edges[char]
u.end_of_word = True
class Solution:
def backtrack(self, row, col, u, board, visited_cells, curr_word, board_words):
m, n = len(board), len(board[0])
v_char = board[row][col]
v = u.edges[v_char]
if v.end_of_word:
board_words.append("".join(curr_word + [v_char]))
v.end_of_word = False
if not v.edges:
del u.edges[v_char]
visited_cells.add((row, col))
curr_word.append(v_char)
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
row2, col2 = row+dr, col+dc
is_valid_cell = (0 <= row2 < m) and (0 <= col2 < n)
if not is_valid_cell:
continue
if (row2, col2) in visited_cells:
continue
if board[row2][col2] not in v.edges:
continue
self.backtrack(row2, col2, v, board, visited_cells, curr_word, board_words)
curr_word.pop()
visited_cells.remove((row, col))
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = Trie()
for word in words:
trie.insert(word)
m, n = len(board), len(board[0])
board_words = []
for row, col in cartesian( range(m), range(n) ):
if board[row][col] not in trie.root.edges:
continue
self.backtrack(row, col, trie.root, board, set(), [], board_words)
return board_words
Since the alphabet consists of just the lowercase English letters, we can mark a visited cell with a non-alphabetic character and get rid of visited_cells — saving space.
from itertools import product as cartesian
class TrieNode:
def __init__(self):
self.end_of_word = False
self.edges = {}
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
u = self.root
for char in word:
if char not in u.edges:
u.edges[char] = TrieNode()
u = u.edges[char]
u.end_of_word = True
class Solution:
def backtrack(self, row, col, u, board, curr_word, board_words):
m, n = len(board), len(board[0])
v_char = board[row][col]
v = u.edges[v_char]
if v.end_of_word:
board_words.append("".join(curr_word + [v_char]))
v.end_of_word = False
if not v.edges:
del u.edges[v_char]
board[row][col] = "*"
curr_word.append(v_char)
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
row2, col2 = row+dr, col+dc
is_valid_cell = (0 <= row2 < m) and (0 <= col2 < n)
if not is_valid_cell:
continue
if board[row2][col2] not in v.edges:
continue
self.backtrack(row2, col2, v, board, curr_word, board_words)
curr_word.pop()
board[row][col] = v_char
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = Trie()
for word in words:
trie.insert(word)
m, n = len(board), len(board[0])
board_words = []
for row, col in cartesian( range(m), range(n) ):
if board[row][col] not in trie.root.edges:
continue
self.backtrack(row, col, trie.root, board, [], board_words)
return board_words
unreasonably effective 
Leave a comment