Check AB in a string

Question

Given a string S, made up of only 'a's and 'b's. Check the string for the following rules. Program in python using recursion.

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

I've tried the following code.

def checkAB(s):
    if len(s) == 0:
        return 1
    if s[0] == 'a':
        if s[1] == 'a' or s[1] == 'b':
            return checkAB(s[2:])
        if s[1] == None:
            return 1
        else:
            return 0
    elif s[0] == 'b':
        if s[1] == 'b' and s[2] == None:
            return checkAB(s[2:])
        elif s[1] == 'b' and s[2] == 'a':
            return 1
        else:
            return 0

s = input()
if s[0] == 'a':
    if checkAB(s[1:]):
        print('true')
    else:
        print('false')
else:
    print('false')

But it shows string index out of range error.

Thanks in advance!

user_599739 · Answer

Fortunately, the rules can be phrased as a regular expression:

start with "a": ^a
continue with an arbitrary amount of "a" or "bba": (a|bba)*
finish at any point or with just "bb": (bb$)?

combined regex: ^a(a|bba)*(bb$)?

(you can probably simplify the regex a bit more, not sure though)

In Python:

import re

def check_rules(s: str) -> bool:
    return bool(re.fullmatch(r"^a(a|bba)*(bb$)?", s))

Some tests:

def test_positive():
    assert check_rules("abba")
    assert check_rules("abbabb")
    assert check_rules("aaabbaabb")
    assert check_rules("abbabbabbaaa")


def test_negative():
    assert not check_rules("aba")
    assert not check_rules("baba")
    assert not check_rules("baabb")
    assert not check_rules("aabbbaa")

cheers

edit: about program in python using recursion - you should always use the right technique for the right job and a recursive function is not useful in this case, because Python has a limit for recursion depth which you may reach pretty fast if you try to analyze a few million characters. A regular expression is an efficient way to analyze a regular language and technically it uses recursion right here (a|bba)* ;)

user_9947326 · Answer

I think this will work fine.

def state2(lst):
    if lst==[]:
        return True
    poped = lst.pop(0)
    if poped == "a":
        return state2(lst)
    else:
        if lst == [] or lst[0] == 'a':
            return False
        if lst[0]=="b":
            lst.pop(0) # removed "BB"
            return state1(lst)

def state1(lst):
    if lst==[]:
        return True
    if lst[0]=="a":
        lst.pop(0)
        return state2(lst)
    return False

Edit:- Easy input

def checkString(inp):
    # print(list(inp))
    return state1(list(inp))

testcases = ["abb","a","ab","abba", "","abbabbb","abbabbaaabbaaabbabb"]
for i in testcases:
    print(checkString(i))

user_5424988 · Answer

A note about the code:

Using s[2] assumes that there is something at the 3rd position, but only s[0] and s[1] are checked in the code causing the IndexError: string index out of range when there is nothing at s[2]

One option is to check for the length and state all the rules and exit clauses.

As an example with some inline comments (maybe it can be shortened but just as an idea)

def checkAB(s):

    # Check for the validity of the input
    if len(s) == 0 or s[0] != 'a':
        return False

    def loop(val):
        # Done processing, all is well
        if len(val) == 0:  
            return True

        # If the first char is a, recurse using the rest of the string
        if val[0] == 'a':
            return loop(val[1:])

        # If there are 3 chars, it can not be bbb
        if len(val) > 2 and val[0] == 'b' and val[1] == 'b' and val[2] == 'b':
            return False

        # If there is a single value left, and that is b it is not ok
        if len(val) == 1 and val[0] == 'b':
            return False

        # If we have bb, recurse using the rest of the string
        if val[0] == 'b' and val[1] == 'b':
            return loop(val[2:])

        # In any other case
        else:
            return False
    return loop(s)

See a Python demo

It is not a solution using recursion, but in case you are interested in another regex solution, you could start with matching on or more times an a.

Then optionally match bb followed by 1 or more a's and end the match with an optional bb

\Aa+(?:bba+)*(?:bb)?\Z

\A Start of string
a+ Match 1 or more times a
(?:bba+)* Optionally repeat bb followed by 1 or more times a
(?:bb)? Optionally match bb
\Z End of string

Regex demo

user_16327441 · Answer

Here You Go......

def check_ab(str):
    if (len(str)==0):
        return True
    
    if (str[0] == 'a'):
        
        if (len(str[1:])>1 and str[1:3] == 'bb'):
            return check_ab(str[3:])
        
        else:
            return check_ab(str[1:])
        
    else:
        return False
    

str = input()
if (check_ab(str)):
    print("true")
else:
    print("false")

user_12154444 · Answer

def checkAB(s):
    if len(s) == 0:
        return 1
    if s[0] == 'a':
        if len(s[1:]) > 1 and s[1:3] == 'bb':
            return checkAB(s[3:])
        else:
            return checkAB(s[1:])
    else:
        return 0

s = input()
if checkAB(s):
    print('true')
else:
    print('false')

This is the solution that I found that suits the given scenario best.

Check AB in a string

5 Answers