basic resursion que of string

Question

i have some set of rules to create a string in a char array

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'

my code is:-

    bool checkAB(char input[]) {
        if(input[0]=='\0'){
            return true;
        }
        if(input[0]!='a'){
            return false;
        }
        bool ans=checkAB(input+1);
        if(input[0]=='a'){
            if(input[1]=='a' || (input[1]=='b' && input[2]=='b') || input[1]==' ')
                return ans && true;
    
            if(input[1]=='b' && input[2]=='b'){
                if(input[3]==' ' || input[3]=='a'){
                    return ans && true;
                }
            }
        }
    
        
        return false;
    }

this code doesn't pass all the test case. can anyone help. pls use recursive approch

Answer 1

Consider what happen when call with "abb"

The first call will execute this line:

bool ans=checkAB(input+1);

which means that we call the function with the input "bb"

That will return FALSE (due to if(input[0]!='a')).

So back in the first call we set ans to FALSE and consequently we end up returning FALSE.

I would think that before the recursive call, you should remove any "bb" following an 'a'.

Something like:

bool checkAB(const char input[]) 
{
    if(input[0] != 'a') return false;   // input must start with an 'a'

    if (input[1] == '\0') return true;  // input was "a"

    if (input[1] == 'b' && input[2] == 'b')
    {
        if (input[3] == '\0') return true;   // input was "abb"
        
        return checkAB(input+3);  // Call without leading "abb"
    }

    return checkAB(input+1);  // Call without leading "a"
}

or you can use strcmp like:

bool checkAB(const char input[]) 
{
    if (input[0] != 'a') return false;
    
    if (strcmp(input, "a") == 0) return true;
    if (strcmp(input, "abb") == 0) return true;

    if (input[1] == 'b' && input[2] == 'b') return checkAB(input+3);  // Call without leading "abb"

    return checkAB(input+1);  // Call without leading "a"
}