目标
给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 '0' 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：
- i + minJump <= j <= min(i + maxJump, s.length - 1) 且
- s[j] == '0'.
如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。
示例 1：
输入：s = "011010", minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。示例 2：
输入：s = "01101110", minJump = 2, maxJump = 3
输出：false说明：
- 2 <= s.length <= 10^5
- s[i] 要么是 '0' ，要么是 '1'
- s[0] == '0'
- 1 <= minJump <= maxJump < s.length
思路
有一个长度为 n 的二进制字符串 s，开始在位置 0 且该位置的值为 0，从该位置出发每次可以跳跃到 [i + minJump, min(i + maxJump, n - 1)] 中元素值为 0 的位置 j，判断能否到达 n - 1。
定义 dp[i] 表示能否到达下标 i，如果 dp[i] = true，标记 [Math.max(j, i + minJump), Math.min(n - 1, i + maxJump)] 中元素值为 '0' 的下标，其中 j 表示之前可覆盖的最大下标 + 1。
代码
/**
* @date 2026-05-25 8:50
*/
public class CanReach1871 {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
char[] chars = s.toCharArray();
if (chars[n - 1] != '0') {
return false;
}
boolean[] dp = new boolean[n];
dp[0] = true;
int j = 1;
for (int i = 0; i < n; i++) {
if (dp[i]) {
for (j = Math.max(j, i + minJump); j <= Math.min(n - 1, i + maxJump); j++) {
dp[j] = chars[j] == '0';
}
}
}
return dp[n - 1];
}
}
性能
