Home > Blockchain >  Dynamic programming coding question in Dart (Jump Game 7) (LeetCode)
Dynamic programming coding question in Dart (Jump Game 7) (LeetCode)

Time:12-20

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.

  •  Tags:  
  • dart
  • Related