1. 題目來(lái)源
- 分類：字典樹
- Leetcode212:單詞搜索II
2. 題目描述
給定一個(gè)二維網(wǎng)格 board 和一個(gè)字典中的單詞列表 words，找出所有同時(shí)在二維網(wǎng)格和字典中出現(xiàn)的單詞。
單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。
示例:
輸入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
輸出: ["eat","oath"]
說(shuō)明:你可以假設(shè)所有輸入都由小寫字母 a-z 組成。
3. 解題思路
根據(jù)Trie Tree(字典樹/前綴樹/單詞查找樹)對(duì)Trie基本結(jié)構(gòu)的描述，編寫構(gòu)建結(jié)點(diǎn)，以及構(gòu)建trie樹，以及trie樹的基本操作方法。
初始化trie樹，并以根結(jié)點(diǎn)開始對(duì)words數(shù)組中的單詞進(jìn)行字典樹的創(chuàng)建，完成結(jié)果如下：
構(gòu)建字典樹
遍歷二維網(wǎng)格boards進(jìn)行深度搜索，對(duì)字典樹路徑進(jìn)行匹配。當(dāng)board[i][j]與node.next[x]不匹配時(shí)，node.next[ord(board[i][j]) - ord('a')] == None, 直接返回，若匹配，則把當(dāng)前board[i][j]標(biāo)記為已經(jīng)過(guò)，之后進(jìn)行深度優(yōu)先遍歷，并把board[i][j]加入經(jīng)過(guò)路徑path，當(dāng)node.isEnd == True時(shí)，此路徑匹配結(jié)束，并把此路徑加入最后結(jié)果集中，并把當(dāng)前結(jié)點(diǎn)node.isEnd置為False。
4. 編程實(shí)現(xiàn)
Python
class TrieNode:
def __init__(self):
self.isEnd = False
self.next = [None for i in range(26)]
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, words):
node = self.root
for i in range(len(words)):
if node.next[ord(words[i]) - ord('a')] == None:
node.next[ord(words[i]) - ord('a')] = TrieNode()
node = node.next[ord(words[i]) - ord('a')]
node.isEnd = True
def search(self, words):
node = self.root
for i in range(len(words)):
if node.next[ord(words[i]) - ord('a')] == None:
return False
node = node.next[ord(words[i]) - ord('a')]
return node.isEnd
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = Trie()
res = []
node = trie.root
# 構(gòu)建字典樹
for word in words:
trie.insert(word)
# 深度搜索boards進(jìn)行路徑匹配
for i in range(len(board)):
for j in range(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res
def dfs(self, board, node, i, j, path, res):
#結(jié)點(diǎn)路徑匹配完畢，把存在路徑加入結(jié)果集中
if node.isEnd:
res.append(path)
#對(duì)已經(jīng)匹配完成的路徑，避免二次匹配
node.isEnd = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] == '#':
return
temp = board[i][j]
node = node.next[ord(temp) - ord('a')]
if not node:
return
board[i][j] = '#'
self.dfs(board, node, i + 1, j, path + temp, res)
self.dfs(board, node, i - 1, j, path + temp, res)
self.dfs(board, node, i, j + 1, path + temp, res)
self.dfs(board, node, i, j - 1, path + temp, res)
# 便于回溯
board[i][j] = temp
