python - 反转字符串的就地递归解决方案

Question

我正在从 leetcode 的特色教程中学习递归基础知识 Recursion I

第一个练习是反转字符串 Reverse String - LeetCode

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

公认的解决方案是

class Solution:
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        #base case
        if len(s) <= 1:
            return s
        #recur case 
        elif len(s) >= 2:
            n=len(s)
            return self.reverseString(s[n//2:])+self.reverseString(s[:n//2])

解决方案的两个问题:

1、不就地修改

2、递归地对字符串进行切片是很昂贵的。

作为改进的第一步，引入参数lo和hi来存储索引

class Solution:
    def reverseString(self, s, lo=0, hi=None):
        """
        :type s: str
        :rtype: None
        """
        if hi == None:
            hi = len(s)
      #base case
        if hi <= 1:
            return s

        #recur case 
        elif hi >= 2:
            mid = hi // 2
            left = self.reverseString(s, lo, mid)
            right = self.reverseString(s, mid, hi)
            return left + right               

报错

　RecursionError: maximum recursion depth exceeded in comparison

---

Ran 1 test in 0.005s

W 有什么问题吗？

Answer 1

要在没有空间的情况下执行此操作，您需要交换。您不能添加数组切片。而不是在中间拆分索引，这永远不会让您交换相反的对(在基本情况下除外)。

如果您直观地想象递归，就可以看到它。你从一个像这样的列表开始:

1, 2, 3, 4
^        ^ <-- these need to swap in a reverse

但是在你第一次递归调用之后，你把它分成了:

---- | ----
1, 2   3, 4
^         ^  <-- these still need to be swapped, bu when?

现在分支一无法到达分支二中的 4 进行交换，除非在递归展开时有一种不明显的方法来进行交换。

相反，您可以(更容易地)从两端引导索引并边走边交换。那么你的基本情况就是他们在中间相遇的时候:

class Solution:
    def reverseString(self, s, lo=0, hi=None):
        if hi == None:
            hi = len(s) - 1

        if hi <= lo:
            return s

        s[lo], s[hi] = s[hi], s[lo]
        return self.reverseString(s, lo + 1, hi - 1)


s = Solution()
s.reverseString([1, 2, 3, 4])
# [4, 3, 2, 1]
s.reverseString([1, 2, 3, 4, 5])
#[5, 4, 3, 2, 1]