Design a data structure that supports the following two operations:
void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
class Node:
def __init__(self):
self.children = collections.defaultdict(Node)
self.isWord = False
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node()
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
p = self.root
for ch in word:
p = p.children[ch]
p.isWord = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
p = self.root
for i, ch in enumerate(word):
if ch == '.':
for j in range(26):
ch_new = chr(ord('a') + j)
if p.children[ch] and self.search(word[:i] + ch_new + word[i+1:]):
return True
return False
else:
if not p.children[ch]:
return False
p = p.children[ch]
return p.isWord
212 Word Search II
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.
Use Trie to store words
DFS search
A boolean table to record the route
Time: num is number of words, k is avg len of a word.
Building trie is O(num*k), searching is O(n*m*4^k)
from collections import defaultdict
class Node:
def __init__(self):
self.children = defaultdict(Node)
self.word = None
class wordDict():
def __init__(self):
self.root = Node()
def insert(self, word):
p = self.root
for ch in word:
p = p.children[ch]
p.word = word
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
self.ans= []
self.board = board
w = wordDict()
for word in words:
w.insert(word)
self.m, self.n = len(board), len(board[0])
for i in range(self.m):
for j in range(self.n):
self.backtrack(i, j, w.root)
return sorted(self.ans)
def backtrack(self, i, j, node):
c = self.board[i][j]
if c not in node.children: return
if node.children[c].word and node.children[c].word not in self.ans:
self.ans.append(node.children[c].word)
self.board[i][j] = '#'
for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
y, x = i+dy, j+dx
if not (0 <= y < self.m and 0 <= x <self.n) or self.board[y][x] == '#': continue
self.backtrack(y, x, node.children[c])
self.board[i][j] = c