212.Word Search II
Tags: [graph], [trie], [prefix_tree], [tree], [graph], [DFS], [backtracking], [pruning]
Com: {g}
Link: https://leetcode.com/problems/word-search-ii/\#/description
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.
For example,
Given words=["oath","pea","eat","rain"]and board=
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Return["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem:Implement Trie (Prefix Tree)first.
Solution: Trie, Prefix Tree, DFS, Backtracking
class Solution(object):
class TrieNode(object):
def __init__(self):
self.end_of_w = False
self.children = {}
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
if not board or not board[0] or not words:
return []
trie_root = self.TrieNode()
for w in words:
self.insert_w(trie_root, w)
rows, cols = len(board), len(board[0])
visited = [[False] * cols for _ in xrange(rows)]
rest = set()
buff = []
for r in xrange(rows):
for c in xrange(cols):
self.dfs(board, rows, cols, r, c, trie_root, buff, rest, visited)
return list(rest)
def insert_w(self, root, w):
curr = root
for i in xrange(len(w)):
c = w[i]
if c not in curr.children:
curr.children[c] = self.TrieNode()
curr = curr.children[c]
curr.end_of_w = True
def dfs(self, board, rows, cols, row, col, trie_root, buff, rest, visited):
if board[row][col] not in trie_root.children:
return
buff.append(board[row][col])
visited[row][col] = True
next_node = trie_root.children[board[row][col]]
if next_node.end_of_w:
rest.add(''.join(buff))
# iterate top, left, bottom, right:
directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
for d in directions:
r, c = row + d[0], col + d[1]
if 0 <= r < rows and 0 <= c < cols and not visited[r][c]:
self.dfs(board, rows, cols, r, c, next_node, buff, rest, visited)
visited[row][col] = False
buff.pop()
Revelation:
- There is a new way to design Trie (prefix tree).
- Using Trie to do pruning when we do DFS and backtracking.
Note:
- Time complexity = O(n * k + (rows * cols) * (rows * cols)) = O(n*k + (rows * cols)^2), n is the number of words, k is the max length of words.
Time Limited Exceeded:
class Solution(object):
class Trie(object):
class TrieNode(object):
def __init__(self):
self.end_of_w = False
self.children = {}
def __init__(self, words):
self.root = self.TrieNode()
for w in words:
self.__add_w(w)
def __add_w(self, w):
curr = self.root
for i in xrange(len(w)):
c = w[i]
if c not in curr.children:
curr.children[c] = self.TrieNode()
curr = curr.children[c]
if i == len(w) - 1:
curr.end_of_w = True
def search(self, w):
# return -1: not found
# return 0: found prefix
# return 1: found word
curr = self.root
for i in xrange(len(w)):
c = w[i]
if c not in curr.children:
return -1
curr = curr.children[c]
return 1 if curr.end_of_w else 0
def delete(self, w):
if not w:
return True
stack = []
curr = self.root
for c in w:
if c not in curr.children:
return False
stack.append(curr)
curr = curr.children[c]
curr.end_of_w = False
index = len(w) - 1
while stack:
curr = stack.pop()
if len(curr.children[w[index]].children) == 0:
del curr.children[w[index]]
index -= 1
return True
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
if not board or not board[0] or not words:
return []
trie = self.Trie(words)
num_of_rows = len(board)
num_of_cols = len(board[0])
visited = [[False for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
rest = set()
buff = []
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
self.dfs(board, num_of_rows, num_of_cols, row, col, buff, rest, visited, trie)
return list(rest)
def dfs(self, board, num_of_rows, num_of_cols, row, col, buff, rest, visited, trie):
buff.append(board[row][col])
visited[row][col] = True
w = ''.join(buff)
search_rest = trie.search(w)
if search_rest == -1:
visited[row][col] = False
buff.pop()
return
elif search_rest == 1:
rest.add(w)
trie.delete(w)
# iterate four directions
# top, left, bottom, right
directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
for d in directions:
r, c = row + d[0], col + d[1]
if 0 <= r < num_of_rows and 0 <= c < num_of_cols and not visited[r][c]:
self.dfs(board, num_of_rows, num_of_cols, r, c, buff, rest, visited, trie)
visited[row][col] = False
buff.pop()
Revelation:
- Remember the way how to delete the word from Trie.
Time Limited Exceeded:
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
if not board or not board[0] or not words:
return []
num_of_rows = len(board)
num_of_cols = len(board[0])
visited = [[False for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
rest = []
for w in set(words):
if self.search(w, board, num_of_rows, num_of_cols, visited):
rest.append(w)
return rest
def search(self, w, board, num_of_rows, num_of_cols, visited):
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
if board[row][col] != w[0]:
continue
if self.dfs(board, num_of_rows, num_of_cols, row, col, w, 0, visited):
return True
return False
def dfs(self, board, num_of_rows, num_of_cols, row, col, w, index, visited):
# base case
if index == len(w) - 1:
return True
visited[row][col] = True
# iterate four directions:
# top, left, bottom, right
directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
for d in directions:
r, c = row + d[0], col + d[1]
if 0 <= r < num_of_rows and 0 <= c < num_of_cols and not visited[r][c] and board[r][c] == w[index + 1]:
if self.dfs(board, num_of_rows, num_of_cols, r, c, w, index + 1, visited):
visited[row][col] = False
return True
visited[row][col] = False
return False