Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example:
Input:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Output: ["eat","oath"]
Note:
You may assume that all inputs are consist of lowercase letters a-z.
My code:
class Trie():
def __init__(self):
self.children = {} # dict im using because predefined 26 letter memory creation can be avoided
self.flag = False # To represent that words ends of current node
def insert(self, word):
node = self
for c in word:
if c not in node.children:
node.children[c] = Trie()
node = node.children[c]
node.children['$'] = Trie()
node.flag = True
class Solution():
def createTrieWithWords(self, wordList):
result = Trie()
for word in wordList:
result.insert(word)
return result
def dfs(self, board, row, col, trie, res, prefix):
c = board[row][col]
if c == '#' or c not in trie.children: # recursive breaking condition
return
trie = trie.children[c]
if '$' in trie.children: # modified a bit to make sure word reaches it end
res.append(prefix + c)
board[row][col] = '#'
if (row > 0): self.dfs(board, row - 1, col, trie, res, prefix + c)
if (col > 0): self.dfs(board, row, col - 1, trie, res, prefix + c)
if (row < len(board) - 1): self.dfs(board, row + 1, col, trie, res, prefix + c)
if (col < len(board[0]) - 1): self.dfs(board, row, col + 1, trie, res, prefix + c)
board[row][col] = c
def findWords(self, board, words):
trie = self.createTrieWithWords(words)
result = []
for row in range(len(board)): # need to visit all character
for col in range(len(board[0])):
self.dfs(board, row, col, trie, result, '')
return list(set(result))