Python: использование рекурсии, чтобы увидеть, является ли одна строка вращением другой

Question

Я попробовал код ниже, но он не работает.Я получаю сообщение об ошибке «RecursionError: превышена максимальная глубина рекурсии в сравнении».

def rot(str1, str2):
    if str1 == str2:
        return True
    else:
        for i, j in enumerate(str1):
            for k, l in enumerate(str2):
                if j == l:
                    a = str1
                    b = str2[k:] + str2[:k]
                    rot(a, b)
        return False

print(rot('ab', 'ba'))

Answer 1

Существует простой, но не обязательно очевидный способ проверить, является ли строка b вращением строки a.Убедитесь, что длины совпадают и удваиваются a.Если b является подстрокой a + a, у вас есть вращение:

def rotation(a, b):
    return len(a) == len(b) and b in a + a

Это стоит доказать себе вручную, например, проверить вращения hello в hellohello.

---

Что касается вашего кода, я не понимаю, как вложенные циклы или рекурсия являются полезными механизмами для решения проблемы.С одной стороны, нет базового случая, поэтому стек дует.Вам понадобится параметр индекса, чтобы отслеживать, сколько вращений было выполнено.

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

def rot(str1, str2):
    if len(str1) == len(str2):
        for i in range(len(str1)):
            str2 = str2[-1] + str2[:-1]

            if str2 == str1:
                return True

    return False

Времясложность для первого решения является линейной, а для второго - экспоненциальной.

Попробуйте!

Answer 2

Вы забыли return rot(a, b)

def rot(str1, str2):
    if str1 == str2:
        return True
    else:
        for i, j in enumerate(str1):
            for k, l in enumerate(str2):
                if j == l:
                    a = str1
                    b = str2[k:] + str2[:k]
                    return rot(a, b)  #returns the value of recursion
        return False

print(rot('ab', 'ba'))