Рекурсивное изменение строки в Python

Question

Я пытаюсь рекурсивно перевернуть строку в Python, однако, это решение не работает

def reverseString(self, s):
    """
    :type s: List[str]
    :rtype: None Do not return anything, modify s in-place instead.
    """
    if len(s) == 0:
        return s
    s[0], s[-1] = s[-1], s[0]
    self.reverseString(s[1:-1])

Для примера ввода ["h", "e", "l", " l "," o "], я получаю вывод [" o "," e "," l "," l "," h "]. Кто-нибудь может объяснить, почему это не работает?

Answer 1

def reverse(s): 
    if len(s) == 0: 
        return s 
    return reverse(s[1:]) + s[0]

Ваше базовое состояние правильное. Но ваш рекурсивный вызов сложный и не неправильный.

Answer 2

def reverse(s):
    if len(s) == 0:
        return ""
    return s[-1] + reverse(s[:-1])

s = ["h","e","l","l","o"]

[letter for letter in reverse(s)] # prints ['o', 'l', 'l', 'e', 'h']

Вы пытаетесь поменять местами первый и последний элементы, затем второй и последний перед элементом и так далее. Вы должны также рассмотреть случай, когда существует нечетное количество элементов, в конечном итоге базовый случай будет содержать всего 1 элемент, поэтому вам нужно включить базовый случай для len(s) == 0 or len(s)==1.

Я исправил ваш код ниже:

def reverse(s):
    if len(s) == 0 or len(s)==1:
        return s
    return s[-1] + reverse(s[1:-1]) + s[0]

[item for item in reverse(''.join(s))] # prints ['o', 'l', 'l', 'e', 'h']

Answer 3

s[0], s[-1] = s[-1], s[0]

Это изменяет список ввода. Похоже, что вы намереваетесь поменять местами два значения на входе с данным вызовом и использовать рекурсию для покрытия каждой необходимой пары значений.

self.reverseString(s[1:-1])

Это делает рекурсивный вызов для только что созданного list , а игнорирует результат . Он не заменяет больше содержимого из исходного списка.

Нет причин изменять ввод на месте. Это не простое решение и ограничивает виды последовательностей, которые вы можете обрабатывать. В общем, вы хотите, чтобы рекурсивные функции генерировали новые значения и оставляли свои входные данные в покое - это намного , чтобы легче рассуждать о них таким образом. (Кроме того, вы можете обрабатывать строки и кортежи автоматически.)

Один простой подход заключается в следующем: мы признаем, что первый символ ввода должен стоять последним в выводе, а затем мы можем получить оставшуюся часть строки с помощью реверсирование остальной части ввода - что мы можем сделать, сделав рекурсивный вызов для остальной части ввода. Это естественно приводит к решению @ HarshalParekh.

Answer 4

Проблема с вашим кодом в том, что reverseString(s[1:-1]) создает новую копию списка, и то, что вы делаете с этим, не влияет на список на текущем уровне рекурсии.

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

def reverseString(s):
    if len(s) <= 1:
        return s
    return s[-1] + reverseString(s[1:-1]) + s[0]

print(reverseString('hello'))

Вывод:

olleh