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

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2024/04/03 11:06)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串88/1548 (看更多)

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 ---------------------------------------- -- https://i.imgur.com/Df746ya.jpg