You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:
i minJump <= j <= min(i maxJump, s.length - 1), and
s[j] == '0'.
Return true if you can reach index s.length - 1 in s, or false otherwise.
Example 1:
Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3.
In the second step, move from index 3 to index 5.
Example 2:
Input: s = "01101110", minJump = 2, maxJump = 3
Output: false
Constraints:
2 <= s.length <= 105
s[i] is either '0' or '1'.
s[0] == '0'
1 <= minJump <= maxJump < s.length
I have done the above question in Dart. But I am not getting proper output. I request you all to please send me the solution of this question as I am new to dart. I am attaching my code which I have done.
class Solution {
bool canReach(String s, int minJump, int maxJump) {
int N = s.length;
Vector<int> good(N);
good[0] = 1;
int M = 0;
for (int i=0; i<N; i ) {
if (s[i] == '0' & a[i]) {
int l = i minJump;
int r = min(N-1, i maxJump);
for (int j=max(l, M); j<=r; j ) {
good[j] = 1;
}
M = r 1;
if (M >= N) break;
}
}
return good.back() == 1 & s.back() == '0';
}
};
CodePudding user response:
I could not really read your code or understand your approach so I have made an attempt from scratch with a recursive design with some documentation. You have not posted that many test cases so I have only tested with a few:
bool canReach(String string, int minJump, int maxJump, [int startIndex = 0]) {
// We stands at the end of the string and stands on a `0` so home is reached
if (string.length == startIndex 1 && string[startIndex] == '0') {
return true;
}
// Go though each jump size
for (var jump = minJump; jump <= maxJump; jump ) {
final newPos = startIndex jump;
// If we have jumped over the length of the string, we just stop with
// further jumps.
if (newPos > string.length - 1) {
break;
}
// If we have jumped to a `0` we should check this as a candidate
if (string[newPos] == '0') {
// Recursive call from our new position
if (canReach(string, minJump, maxJump, newPos)) {
// If we reached home with our solution, we just stops here
return true;
}
}
}
// If we did not reached a `true` going though all jump size candidates,
// we mark our attempted solution as failed.
return false;
}
void main() {
print(canReach('011010', 2, 3)); // true
print(canReach('01101110', 2, 3)); // false
print(canReach('01101110', 2, 4)); // true
}
Please tell me if there are any problems or if you have any questions about how this code works.