1. 題目來源
- 分類：字典樹
- Leetcode212:單詞搜索II
2. 題目描述
給定一個二維網(wǎng)格 board 和一個字典中的單詞列表 words，找出所有同時在二維網(wǎng)格和字典中出現(xiàn)的單詞。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內(nèi)的字母在一個單詞中不允許被重復(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"]
說明:你可以假設(shè)所有輸入都由小寫字母 a-z 組成。
3. 解題思路
根據(jù)Trie Tree(字典樹/前綴樹/單詞查找樹)對Trie基本結(jié)構(gòu)的描述，編寫構(gòu)建結(jié)點，以及構(gòu)建trie樹，以及trie樹的基本操作方法。
初始化trie樹，并以根結(jié)點開始對words數(shù)組中的單詞進(jìn)行字典樹的創(chuàng)建，完成結(jié)果如下：
構(gòu)建字典樹
遍歷二維網(wǎng)格boards進(jìn)行深度搜索，對字典樹路徑進(jìn)行匹配。當(dāng)board[i][j]與node.next[x]不匹配時，node.next[ord(board[i][j]) - ord('a')] == None, 直接返回，若匹配，則把當(dāng)前board[i][j]標(biāo)記為已經(jīng)過，之后進(jìn)行深度優(yōu)先遍歷，并把board[i][j]加入經(jīng)過路徑path，當(dāng)node.isEnd == True時，此路徑匹配結(jié)束，并把此路徑加入最后結(jié)果集中，并把當(dāng)前結(jié)點node.isEnd置為False。
4. 編程實現(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é)點路徑匹配完畢，把存在路徑加入結(jié)果集中
if node.isEnd:
res.append(path)
#對已經(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
