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

➣ Reading Time: 9 minutes

題目出處

79. Word Search

難度

medium

個人範例程式碼

DIRECTIONS = [
        (1, 0),
        (-1, 0),
        (0, 1),
        (0, -1)
        ]

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False

        # first point
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0] and self.dfs(board, word[1:], i, j, {(i,j)}):
                    return True
        return False # after all search

    def dfs(self, board, word, i, j, visited):
        # end of recursion
        if not word:
            return True

        # define and split
        for (dx, dy) in DIRECTIONS:
            next_x, next_y = i+dx, j+dy
            # print(next_point)
            if self.is_valid_point(next_x, next_y, board, visited, word[0]):
                visited.add((next_x, next_y))
                if self.dfs(board, word[1:], next_x, next_y, visited):
                    return True
                visited.remove((next_x, next_y)) # backtracking

        return False

#     def dfs(self, board, word, start_point, visited):
#         # end of recursion
#         if not word:
#             return True

#         # define and split
#         for (dx, dy) in DIRECTIONS:
#             next_point = (start_point[0]+dx, start_point[1]+dy)
#             # print(next_point)
#             if self.is_valid_point(next_point, board, visited, word[0]):
#                 visited.add(next_point)
#                 if self.dfs(board, word[1:], next_point, visited):
#                     return True
#                 visited.remove(next_point) # backtracking

#         return False

    def is_valid_point(self, x, y, board, visited, word):
        if (x, y) in visited:
            return False
        r = len(board)
        c = len(board[0])
        return 0 <= x < r and 0 <= y < c and board[x][y] == word

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

算法說明

這題是學習矩陣內的四方向搜尋,類似題目可參考:

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

不過這題目有個難點是很容易 TLE,在處理上我們需要稍微優化一下:

優化比較的項目長度

例如說可能不要比較整個 prefix,而是只比較單一個 word

不要使用 tuple 實作

我註解掉的部分是使用 tuple 實作的,概念上應該會更清楚,
但因為會影響到時間,後來取消掉註解後才沒有 TLE

input handling

當沒有 matrix 時,return False

Boundary conditions

搜尋到目標後,就可以 return True 了。
沿路上發現字母不對,就直接 return False

Reference

Howard Weng
Howard Weng

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

文章: 693

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