Word Search II (Deprecated)
Given a 2-D array of characters and a list of valid words, find the number of words on the board. Tags: Recursion, Search, Trees
Try It!
Discussion
Video
Solution
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
visited = [[False for c in range(len(board[0]))] for r in range(len(board))]
ans = set()
trie = {}
for word in words:
level = trie
for letter in word:
if letter not in level:
level[letter] = {}
level = level[letter]
level['#'] = '#'
for r in range(len(board)):
for c in range(len(board[0])):
cur = ''
self.dfs(board, visited, r, c, trie, cur, ans)
return list(ans)
def dfs(self, board, visited, r, c, trie, cur, ans):
if '#' in trie:
ans.add(cur)
if r < 0 or r >= len(board):
return
if c < 0 or c >= len(board[0]):
return
if visited[r][c]:
return
if board[r][c] not in trie:
return
letter = board[r][c]
if letter in trie:
cur += letter
trie = trie[letter]
visited[r][c] = True
self.dfs(board, visited, r + 1, c, trie, cur, ans)
self.dfs(board, visited, r - 1, c, trie, cur, ans)
self.dfs(board, visited, r, c + 1, trie, cur, ans)
self.dfs(board, visited, r, c - 1, trie, cur, ans)
visited[r][c] = False