題目出處

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

• 单词搜索 · Word Search