原題
給出一個(gè)由小寫字母組成的矩陣和一個(gè)字典辅搬。找出所有同時(shí)在字典和矩陣中出現(xiàn)的單詞唯沮。一個(gè)單詞可以從矩陣中的任意位置開始，可以向左/右/上/下四個(gè)相鄰方向移動(dòng)。
樣例
給出矩陣：
doaf
agai
dcan
和字典：
{"dog", "dad", "dgdg", "can", "again"}
返回 {"dog", "dad", "can", "again"}
解題思路
- 最直接但是會(huì)超時(shí)的方法 - 先把字典做成hashMap介蛉，對(duì)每一個(gè)點(diǎn)DFS萌庆，每增加一個(gè)字符就去hashMap查找是否存在。一共m*n個(gè)點(diǎn)币旧，每次DFS復(fù)雜度是O(m*n)践险，所以總的時(shí)間復(fù)雜度是O(m*n * m*n)
- 可行解 - 把給出的字典變成Trie樹，Trie樹可以檢查前綴吹菱，hashMap做不到巍虫。檢查前綴的時(shí)候，如果發(fā)現(xiàn)某個(gè)前綴不存在鳍刷，就可以不用繼續(xù)DFS了占遥，相當(dāng)于剪枝
- 注意：當(dāng)不必要的check增多時(shí)，會(huì)導(dǎo)致TLE
# 超時(shí)
if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] == 0 or cur_node == None:
# 免去兩個(gè)不必要的check倾剿，不超時(shí)
if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]):
完整代碼
class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.children = {}
self.IsWord = False
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
node = self.root
for letter in word:
child = node.children.get(letter)
if child is None:
child = TrieNode()
node.children[letter] = child
node = child
node.IsWord = True
class Solution(object):
def __init__(self):
self.result = []
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
trie = Trie()
for word in words:
trie.insert(word)
for row_num in range(len(board)):
for col_num in range(len(board[0])):
self.search(board, row_num, col_num, trie.root, "")
return self.result
def search(self, board, x, y, cur_node, word):
if cur_node.IsWord:
self.result.append(word)
cur_node.IsWord = False
if not (x < 0 or x >= len(board) or y < 0 or y >= len(board[0])):
temp = board[x][y]
cur_node = cur_node.children.get(temp)
if cur_node:
board[x][y] = "#"
self.search(board, x+1, y, cur_node, word+temp)
self.search(board, x-1, y, cur_node, word+temp)
self.search(board, x, y+1, cur_node, word+temp)
self.search(board, x, y-1, cur_node, word+temp)
board[x][y] = temp
