难度: Hard
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(row * col * max_len(words))- 空间复杂度: O(row * col)******
一看到就实现了一个DFS，超时了
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 words:
return []
self.words = set(words)
self.max_len_word = max(len(word) for word in self.words)
self.res = []
self.row = len(board)
self.col = len(board[0]) if self.row else 0
for i in range(self.row):
for j in range(self.col):
self.dfs(board, board[i][j], i, j, set([(i,j)]))
return self.res
def dfs(self, board, path, x, y, visited):
if path in self.words:
self.res.append(path)
self.words.remove(path)
self.max_len_word = max(len(word) for word in self.words) if self.words else 0
if len(path) >= self.max_len_word:
return
if x - 1 >= 0 and (x-1, y) not in visited:
self.dfs(board, path+board[x-1][y], x-1, y, visited | set([(x-1, y)]))
if y - 1 >= 0 and (x, y-1) not in visited:
self.dfs(board, path+board[x][y-1], x, y-1, visited | set([(x, y-1)]))
if x + 1 <= self.row - 1 and (x+1, y) not in visited:
self.dfs(board, path+board[x+1][y], x+1, y, visited | set([(x+1, y)]))
if y + 1 <= self.col - 1 and (x, y+1) not in visited:
self.dfs(board, path+board[x][y+1], x, y+1, visited | set([(x, y+1)]))
思路 2 - 时间复杂度: O(row * col * max_len(words))- 空间复杂度: O(len(words) * word_len)******
看到这种字符串搜索，要想到利用trie树, beats 29.36%
class TrieNode(object):
def __init__(self):
self.children = dict()
self.isWordEnd = False
def buildTrie(self, words):
for word in words:
curr = self
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.isWordEnd = True
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 words:
return []
root = TrieNode()
root.buildTrie(words)
self.res = set()
self.row = len(board)
self.col = len(board[0]) if self.row else 0
def dfs(x, y, node, path):
if node.isWordEnd:
self.res.add(path)
if x < 0 or x >= self.row or y < 0 or y >= self.col:
return
if board[x][y] in node.children:
c = board[x][y]
board[x][y] = '*' # backtracking
dfs(x + 1, y, node.children[c], path + c)
dfs(x - 1, y, node.children[c], path + c)
dfs(x, y + 1, node.children[c], path + c)
dfs(x, y - 1, node.children[c], path + c)
board[x][y] = c
for i in range(self.row):
for j in range(self.col):
dfs(i, j, root, '')
return list(self.res)思路 3 - 时间复杂度: O(row * col * max_len(words))- 空间复杂度: O(len(words) * word_len)******
看到一种更简单的trie实现模式，参考yang.zheng.904
beats 57.44%
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 words:
return []
# build trie
trie = {}
for w in words:
t = trie
for c in w:
if c not in t:
t[c] = {}
t = t[c]
t['#'] = '#'
self.res = set()
self.row = len(board)
self.col = len(board[0]) if self.row else 0
def dfs(x, y, node, path):
if '#' in node:
self.res.add(path)
if x < 0 or x >= self.row or y < 0 or y >= self.col:
return
if board[x][y] in node:
c = board[x][y]
board[x][y] = '*' # backtracking
dfs(x + 1, y, node[c], path + c)
dfs(x - 1, y, node[c], path + c)
dfs(x, y + 1, node[c], path + c)
dfs(x, y - 1, node[c], path + c)
board[x][y] = c
for i in range(self.row):
for j in range(self.col):
dfs(i, j, trie, '')
return list(self.res)