題目出處

• 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，可參考：

【Leetcode】python – [54] Spiral Matrix 個人解法筆記

非常難的題目，最主要難的點是在會 TLE 的部分，特別是 LeetCode 設定的標準，
對使用 python 而言非常的嚴苛。

最主要是實作 Trie 的內容與矩陣的四方向移動，
在矩陣的四方向移動，可以先參考以下比較簡單的題目：

【Leetcode】python – [54] Spiral Matrix 個人解法筆記

注意：可繼續搜尋的項目

例如： [“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