LeetCode 筆記 - 1306. Jump Game III

Posted on

題目在此 1306. Jump Game III

給定一個數列，第 i 個數值表示你可以把 i + arr[i] or i - arr[i] 當作下一個 index
請回傳是否可以找到 value 0

解題思維

如果沒寫過第一題，可以先看 LeetCode 筆記 - 55. Jump Game
如果沒寫過第二題，可以先看 LeetCode 筆記 - 45. Jump Game II

這題型就是附帶條件的 Depth First Search
照著條件實作就可以了

有個實作小細節是可以記錄看過的 index，一但又看到就回傳失敗
因為如果可以找到 value 0，早就回傳 True 了
不會還在這打打鬧鬧

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        if (size := len(arr)) == 1:
            return True
        
        visited = set()
        
        def dfs(index):
            if index < 0 or size <= index:
                return False
            if index in visited:
                return False
            visited.add(index)
            
            if arr[index] == 0:
                return True
            result = dfs(index + arr[index]) or dfs(index - arr[index])

            return result
        
        return dfs(start)

也許你也會想看看