Check AB

 Check AB

Send Feedback

Suppose you have a string, S, made up of only 'a's and 'b's. Write a recursive function that checks if the string was generated using the following rules:

a. The string begins with an 'a'
b. Each 'a' is followed by nothing or an 'a' or "bb"
c. Each "bb" is followed by nothing or an 'a'

If all the rules are followed by the given string, return true otherwise return false.

Input format :

String S

Output format :

'true' or 'false'

Constraints :

1 <= |S| <= 1000
where |S| represents length of string S.

Sample Input 1 :

abb

Sample Output 1 :

true

Sample Input 2 :

abababa

Sample Output 2 :

false

Explanation for Sample Input 2

In the above example, a is not followed by either "a" or "bb", instead it's followed by "b" which results in false to be returned.

bool checkAB(char input[],int n,int s=0)
{
    bool ans=false;
    if(input[n]=='\0')
    {
        return true;
    }
    if(input[n]=='a')
    {
        s=1;
        ans=checkAB(input,n+1,s);
    }
    if(input[n]='b'&&input[n+1]=='b'&&s!=0)
    {
        s=0;
        ans=checkAB(input,n+2,s);
    }
    return ans;
}
bool checkAB(char input[]) {
    // Write your code here
     bool ans;
     //int l=llength(input);
     ans=checkAB(input,0);
     return ans;
    //abababa   abbbb
}

#include <iostream>
using namespace std;

bool checkAB(char input[],int n,int s=0)
{
    bool ans=false;
    if(input[n]=='\0')
    {
        return true;
    }
    if(input[n]=='a')
    {
        s=1;
        ans=checkAB(input,n+1,s);
    }
    if(input[n]='b'&&input[n+1]=='b'&&s!=0)
    {
        s=0;
        ans=checkAB(input,n+2,s);
    }
    return ans;
}
bool checkAB(char input[]) {
    // Write your code here
     bool ans;
     //int l=llength(input);
     ans=checkAB(input,0);
     return ans;
    //abababa   abbbb
}




int main() {
    char input[100];
    bool ans;
    cin >> input;
    ans=checkAB(input);
    if(ans)
        cout<< "true" << endl;
    else
        cout<< "false" << endl;
}