Завершите рекурсию до обнаружения всех состояний - PullRequest
Новая
       85

Завершите рекурсию до обнаружения всех состояний

0 голосов
/ 19 июня 2020

Я написал следующую функцию, и вывод программы правильный. Однако программа обнаруживает все возможные состояния при выполнении рекурсии, что означает, что программа может быть выполнена более эффективно. По сути, мне нужно, чтобы рекурсия завершалась, когда на выходе было True, а не для обнаружения других состояний. Любые идеи приветствуются! 

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)

Описание проблемы выглядит следующим образом:

Даны две строки a и b (b в верхнем регистре). Найдите, возможно ли получить строку b из строки a, используя следующие правила:

  1. Если символ строки строчный, значит, вы разрешили удалить его.

  2. Если символ строки - нижний регистр, то вы можете сделать этот символ в верхнем регистре.

  3. Символ можно пропустить .

Ввод будет следующий: 

1
daBcd
ABC

В то время как вывод должен быть: 

true

1 Ответ

0 голосов
/ 19 июня 2020 
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)

Когда один из флагов имеет значение True, вы можете немедленно вернуть его.

...