Terminate the recursion before discovering all the states

Question

I wrote the following function and the output for the program is correct. However, the program discovers all possible states while doing the recursion, which means the program can be done more efficient. Basically, I need the recursion to terminate when output is True and not to discover other states. Any ideas are appreciated!

checked_strings = []

# idx - current index of string a
# input string a
# output string b
def abbreviation(idx, a, b):
    if a in checked_strings:
        return False
    if idx == len(a):
        return a == b
    flag1 = flag2 = False
    if a[idx].islower():
        new_string1 = a[:idx] + a[idx+1:]
        flag1 = abbreviation(idx, new_string1, b)
        if not flag1:
            checked_strings.append(new_string1)
        new_string2 = a[:idx] + a[idx].upper() + a[idx+1:]
        flag2 = abbreviation(idx + 1, new_string2, b)
        if not flag2:
            checked_strings.append(new_string2)
    return flag1 or flag2 or abbreviation(idx + 1, a, b)

The description of the problem is as follows:

Given two strings a and b (b in upper case). Find if it is possible to obtain string b from string a using the following rules:

1. If the character of the string is lower case, then you allowed to remove it.

2. If the character of the string is lower case, then you are allowed to make this character upper case.

3. The character can be skipped.

The input is as follows:

1
daBcd
ABC

While the output should be:

true 

Answer 1

checked_strings = []

# idx - current index of string a
# input string a
# output string b
def abbreviation(idx, a, b):
    if a in checked_strings:
        return False
    if idx == len(a):
        return a == b
    flag1 = flag2 = False
    if a[idx].islower():
        new_string1 = a[:idx] + a[idx+1:]
        flag1 = abbreviation(idx, new_string1, b)
        if flag1:
            return True
        else
            checked_strings.append(new_string1)
        new_string2 = a[:idx] + a[idx].upper() + a[idx+1:]
        flag2 = abbreviation(idx + 1, new_string2, b)
        if flag2:
            return True
        else
            checked_strings.append(new_string2)
    return abbreviation(idx + 1, a, b)

When one of the flags is True, you can immediately return it.