Re: [閒聊] 每日leetcode已回收

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/04/03 18:09)推噓3(3推 0噓 2→)

留言5則, 3人參與討論串91/1548 (看更多)

※ 引述《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

04/03 18:15, 1年前 , 1^F

04/03 18:15, 1^F

→

sustainer123

04/03 18:17, 1年前 , 2^F

04/03 18:17, 2^F

→

sustainer123

04/03 18:17, 1年前 , 3^F

04/03 18:17, 3^F