Checks whether the end of a given binary string can be reached by selecting a jump value within the given range

A binary string is a string containing only two different types of characters, 0 and 1. Given a binary string and two integers L and R. We can make a jump of size between 'L' and 'R', inclusive, from the index where the string value is '0'. We have to start from the zeroth index and find out if we can reach the last index.

ExampleExample

Input1:
string str = “01001110010”
int L = 2, R = 4
Output: Yes, we can reach the last index.

Explanation

is translated as:

Explanation

We can jump three times from zero index and then two more jumps to 4 so that we get to the final desired index.

Input2:
string str = “01001110010”
int L = 2, R = 3
Output: No, we cannot reach the last index. 

Explanation

is translated as:

Explanation

We can make two jumps, each jump is 2 or 3, if we jump from the 0th index, we either reach the 2nd index or the 3rd index, and then we can only jump to the value With an index of '1', no further jumps can be made.

method one

The Chinese translation of

Idea

is:

Idea

The idea is to apply the concept of dynamic programming. We can maintain an array indicating whether a location is reachable.

If we can reach one position, then the next l to r positions can also be achieved.

Implementation

We will create a function that will take a string, left position, and right position as parameters and return a boolean value.

In this function, we will iterate through the array and use a nested for loop to traverse the range, check whether the current position minus the current range position is reachable, and if it is reachable, the position can be reached.

Eventually, we will return the status of the last index of the DP array, representing the final answer.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
// function to implement the DP concepts 
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results 
   
   // Initiating the first index 
   dp[0] = str[0] == '0'; 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      for(int j = l; j <= r ; j++){
         if(i-j < 0){
            break;
         }
         if(str[i-j] == '1' || dp[i-j] == 0){
            continue;
         }
         else{
            dp[i] = 1;
            break;
         }
      }
   }
   return dp[len-1];
}
int main(){
   string str = "01001110010";
   int l = 2, r = 4; 
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
   else{
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

Output

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

Time complexity and space complexity

The time complexity of the above code is O(N^2), where N is the size of the given string. We used nested for loops, which resulted in a time complexity of N^2.

The space complexity of the above code is O(N) because we use an array of length N to store the DP state.

Method Two

This method is a better version of the previous one, in this method we will maintain an integer to get the number of jumps we can make. On each jump, we can increment the count if the jump is possible, and decrement the count if the jump is not possible at any location.

We will store the data in each index of the DP array and use it later.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results     
   // initiating the first index 
   dp[0] = str[0] == '0';    
   int count = 0; // variable to maintain the count of the jump 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      if (i >= l) {
         count += dp[i - l];
      }
      if (i > r) {
         count -= dp[i -r- 1];
      }
      dp[i] = (count > 0) and (str[i] == '0');
   }
   return dp[len-1];
}

// main function 
int main(){
   string str = "01001110010";
   int l = 2, r = 4;  
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   } else {
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

Output

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

Time complexity and space complexity

The time complexity of the above code is O(N), where N is the size of the given string. We use a single loop to iterate over the string so that the time complexity is linear.

The space complexity of the above code is O(N) because we use an array of length N to store the DP state.

in conclusion

In this tutorial, we implemented a code that determines whether we can reach a given index by starting from the first index and moving a given number of indexes from the index containing '0' in the given string The end of the string. We adopted the dynamic programming method, the time complexity is O(N^2) and O(N), and the space complexity is O(N).

The above is the detailed content of Checks whether the end of a given binary string can be reached by selecting a jump value within the given range. For more information, please follow other related articles on the PHP Chinese website!