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

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

留言11則, 3人參與討論串89/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 : ---------------------------------------- 求救一下照著溫莎思路寫了一下但一直過不了想問一下可能問題在哪 py code: class Solution: def exist(self, board: List[List[str]], word: str) -> bool: m = len(board[0]) n = len(board) l = [] visited = [] for i in range(n): for j in range(m): if board[i][j] == word[0]: l.append((i,j)) def dfs(node,visited,c): visited.append(node) if board[node[0]][node[1]] == word[c]: c += 1 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 x>=0 and x<n and y>=0 and y<m: if board[x][y] == word[c]: return dfs((x,y),visited,c) for e in l: if dfs(e,visited,0) == True: return True return False 另外graph有沒有什麼解題技巧阿寫了一個多禮拜還是不太懂怎麼解感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.142.178 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712135915.A.049.html

推

JIWP

04/03 17:22, 1年前 , 1^F

04/03 17:22, 1^F

→

sustainer123

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

04/03 17:23, 2^F

→

JIWP

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

04/03 17:23, 3^F