【Leetcode】python – [212] Word Search II 個人解法筆記

➣ Reading Time: 13 minutes

題目出處

難度

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 – [79] Word Search 個人解法筆記

非常難的題目,最主要難的點是在會 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 標準到底設定有多硬…

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

★留個言吧!內容有誤或想要補充也歡迎與我討論!