Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/word-search/description
: 79. Word Search
: 給你一個包含字母字元的matrix，求出是否可以找到目標字串word。
: 思路：
: 1.遍歷矩陣，如果board[i][j] = word[0] 則從這個點開始 DFS 搜索所有可能的走法，
:   如果可以走到底就返回 True。
: 2.標記原矩陣或用一個bool[][]紀錄走過的點避免重複走訪，遇到死路的時候把它復原。
: py code：
: ----------------------------------------
: class Solution:
:     def __init__(self):
:         self.dirs = [[1,0],[-1,0],[0,1],[0,-1]]
:     def exist(self, board: List[List[str]], word: str) -> bool:
:         m = len(board)
:         n = len(board[0])
:         for i in range(m):
:             for j in range(n):
:                 if board[i][j] != word[0]:
:                     continue
:                 # DFS
:                 if self.dfs(board, word, i, j, 0):
:                     return True
:         return False
:     def dfs(self, board: List[List[str]], word: str, y: int, x: int, idx:
: int):
:         m = len(board)
:         n = len(board[0])
:         if idx == len(word):
:             return True
:         if y < 0 or y == m or x < 0 or x == n:
:             return False
:         if board[y][x] != word[idx]:
:             return False
:         tmp = board[y][x]
:         board[y][x] = '*'
:         for dir in self.dirs:
:             new_y, new_x = y + dir[0], x + dir[1]
:             if self.dfs(board, word, new_y, new_x, idx + 1):
:                 return True
:         board[y][x] = tmp
:         return False
: ----------------------------------------

照抄大老思路
我本來想說是bfs
結果後面時間炸裂

Python code:
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board[0])
        n = len(board)
        visited = set()

        def dfs(node, visited, c):
            visited.add(node)

            if c == len(word):
                return True
            dx = [0, 0, 1, -1]
            dy = [1, -1, 0, 0]

            for i in range(4):
                x = node[0] + dx[i]
                y = node[1] + dy[i]

                if (x, y) in visited:
                    continue
                else:
                    if 0 <= x < n and 0 <= y < m:
                        if board[x][y] == word[c]:
                            if dfs((x, y), visited, c+1):
                                return True
            visited.remove(node)
            return False

        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0]:
                    if dfs((i, j), visited, 1):
                        return True
        return False

圖真的有夠難 每次遇到都出問題 哭了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.142.178 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712138959.A.91F.html
推 oinishere: 我是DFS欸 大概300ms BFS 多少啊
→ sustainer123: 反正過不了 我沒仔細看
→ sustainer123: 你300 我好像你的十倍以上 哭了
推 oinishere: 寶 我是c++ 你是py 比不了
推 SecondRun: 大師