題目出處
- LeetCode 版本,標準非常高,基本上沒實作出 Trie 一定 TLE:
212. Word Search II LintCode 版本,基本版先通過這個就好 (本文的內容):
132 · Word Search II
難度
hard
個人範例程式碼
from typing import (
List,
)
DIRECTIONS = [
(1, 0),
(0, 1),
(-1, 0),
(0, -1)
]
class TrieNode():
def __init__(self):
self.children = {}
self.isWord = False
class Trie():
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.isWord = True
def search(self, word):
node = self.root
for c in word:
if c in node.children:
node = node.children[c]
else:
return False
return node.isWord
def startswith(self, prefix):
# print(prefix)
node = self.root
for c in prefix:
if c in node.children:
node = node.children[c]
else:
return False
return True
class Solution:
"""
@param board: A list of lists of character
@param words: A list of string
@return: A list of string
"""
def word_search_i_i(self, board: List[List[str]], words: List[str]) -> List[str]:
if not board:
return []
# self.prefix_set = self.make_prefix_set(words)
self.trie = Trie()
for word in words:
self.trie.insert(word)
self.ans = []
for x in range(len(board)):
for y in range(len(board[0])):
self.dfs(board, words, x, y, set(), "")
return self.ans
def dfs(self, board, words, x, y, visited, prefix):
# print(prefix)
# end of recursion
if not words: # all finished
return
if prefix in words:
self.ans.append(prefix[:])
words.remove(prefix[:]) # prevent duplicate
# if prefix != "" and prefix not in self.prefix_set:
if prefix != "" and not self.trie.startswith(prefix):
return
# define and split
if not self.is_in_bound(x, y, board):
return
if (x,y) in visited:
return
visited.add((x, y))
for dx, dy in DIRECTIONS:
self.dfs(board, words, x+dx, y+dy, visited, prefix+board[x][y])
visited.remove((x, y)) # backtracking
def is_in_bound(self, x, y, board):
m, n = len(board), len(board[0])
return 0 <= x < m and 0 <= y < n
# def make_prefix_set(self, words):
# prefix_set = set()
# for word in words:
# for i in range(len(word)):
# prefix_set.add(word[:i+1])
# return prefix_set
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
- 此題目的前一題為「單純找一個單字」就好,並只需要回傳 True/False,可參考:
非常難的題目,最主要難的點是在會 TLE 的部分,特別是 LeetCode 設定的標準,
對使用 python 而言非常的嚴苛。
最主要是實作 Trie 的內容與矩陣的四方向移動,
在矩陣的四方向移動,可以先參考以下比較簡單的題目:
注意:可繼續搜尋的項目
例如: [“app”, “apple”],不能搜尋到 app 就 return,會找不到 apple
input handling
當沒有 matrix 時,return []
Boundary conditions
用 Trie 判斷全部搜尋結果是很簡單的,只是需要各種的搶時間以避免 TLE。
Reference
這邊我試跑 Leetcode 其他人的解答也幾乎都 TLE…,這 Leetcode 標準到底設定有多硬…
- Python dfs solution (directly use Trie implemented).
- 27 lines, uses complex numbers
- [Python] Trie solution with dfs, explained
- 单词搜索 II · Word Search II