Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example 1:
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Example 2:
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 12board[i][j] is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i] consists of lowercase English letters.- All the strings of
words are unique.
## Solution(Python)
```Python
from collections import defaultdict
class TrieNode:
def __init__(self):
self.child = defaultdict(TrieNode)
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode() # root Node
def insert(self, word):
node = self.root
for c in word:
node = node.child[c]
node.end = True
def search(self, word):
node = self.root
for c in ord:
node = node.children.get(c)
if not node:
return False
return node.end
class Solution:
# trie
# store words in trie
# run dfs to find the words
# Time Complexity: O(k*L+M*N*L)
# Space COmplexity: O(K*L+M*N)
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# construct phase
result = []
trie = Trie()
rootNode = trie.root
for word in words:
trie.insert(word)
# search phase
n = len(board)
m = len(board[0])
for i in range(n):
for j in range(m):
# run dfs
self.dfs(board, rootNode, i, j, "", result)
return result
def dfs(self, board, node, i, j, path, result):
if node.end:
result.append(path)
node.end = False
# stopping condition
# out of boundary
# node doesn't exist
if i<0 or i>=len(board) or j < 0 or j >= len(board[0]):
return
currentCell = board[i][j] # using temparry cell to track by current cell value
node = node.child.get(currentCell)
if not node:
return
board[i][j] = "#" # visited cell
# adjacent check on four directions
self.dfs(board, node, i+1, j, path+currentCell, result)
self.dfs(board, node, i-1, j, path+currentCell, result)
self.dfs(board, node, i, j+1, path+currentCell, result)
self.dfs(board, node, i, j-1, path+currentCell, result)
# restore cell value
board[i][j] = currentCell
```