« Check AB recursively

Problem

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.

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14bool checkABHelper(char input[], int start)
15{
16    if (input[start] == '\0')
17    {
18        return true;
19    }
20    if (input[start] != 'a')
21    {
22        return false;
23    }
24    if (input[start + 1] != '\0' && input[start + 2] != '\0')
25    {
26        if (input[start + 1] == 'b' && input[start + 2] == 'b')
27        {
28            return checkABHelper(input, start + 3);
29        }
30    }
31    return checkABHelper(input, start + 1);
32}
33
34bool checkAB(char input[])
35{
36    return checkABHelper(input, 0);
37}
38
39int main()
40{
41    char input[100];
42    cin >> input;
43    bool ans;
44    ans = checkAB(input);
45    if (ans)
46    {
47        cout << "true" << endl;
48    }
49    else
50    {
51        cout << "false" << endl;
52    }
53    return 0;
54}