1871. Jump Game VII

Medium
Description

給定一個二進位字串 s（以 ‘0’ 開頭）和兩個整數 minJump、maxJump。從位置 0 出發，每次可以跳 minJump 到 maxJump 步，但只能落在 ‘0’ 的位置上。判斷能否到達最後一個位置。

Example:

Input: s = “011010”, minJump = 2, maxJump = 3 Output: true

Intuition#

用滑動視窗或前綴和記錄哪些位置可達，避免重複檢查。

  • 暴力 BFS 會超時，因為每個可達位置都要檢查 maxJump - minJump + 1 個後繼
  • 用前綴和或滑動視窗追蹤「可達位置數」，O(1) 判斷某位置是否有可達的前驅
  • 若 [i - maxJump, i - minJump] 範圍內有可達位置且 s[i] == '0'，則 i 可達

Approaches#

1: BFS + 優化#

  • 概念: 用 BFS 搜索，但維護一個指標避免重複掃描已處理的範圍。
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
        val n = s.length
        if (s[n - 1] == '1') return false

        val queue = ArrayDeque<Int>()
        queue.add(0)
        var farthest = 0

        while (queue.isNotEmpty()) {
            val i = queue.removeFirst()
            val start = maxOf(i + minJump, farthest + 1)
            val end = minOf(i + maxJump, n - 1)
            for (j in start..end) {
                if (s[j] == '0') {
                    if (j == n - 1) return true
                    queue.add(j)
                }
            }
            farthest = maxOf(farthest, end)
        }
        return false
    }
}

⭐2: 前綴和 DP#

  • 概念: dp[i] 表示位置 i 是否可達。用前綴和記錄 dp 中的可達位置數，O(1) 查詢某範圍內是否有可達位置。
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Solution {
    fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
        val n = s.length
        if (s[n - 1] == '1') return false

        val dp = BooleanArray(n)
        dp[0] = true
        var reachable = 0 // 滑動視窗內可達位置的數量

        for (i in 1 until n) {
            if (i >= minJump) reachable += if (dp[i - minJump]) 1 else 0
            if (i > maxJump) reachable -= if (dp[i - maxJump - 1]) 1 else 0
            dp[i] = s[i] == '0' && reachable > 0
        }
        return dp[n - 1]
    }
}

🔑 Takeaways#

  • Pattern: 滑動視窗 + DP — 用累計計數避免重複掃描跳躍範圍
  • 關鍵技巧: 前綴和/滑動視窗將「範圍內是否有可達位置」的查詢降到 O(1)