我正在从leetcode的特色教程Recursion I学习递归基础知识
第一个练习是扭转字符串Reverse String - LeetCode
编写一个反转字符串的函数。输入字符串以字符
char[]的数组形式给出。不要为另一个数组分配额外的空间，必须通过使用O（1）额外内存修改输入数组来实现此目的。
您可以假设所有角色都由printable ascii characters组成。
例1：
Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]例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：比较时超出了最大递归深度
以0.005s进行1次测试
有什么问题？
要做到这一点没有空间，你需要交换。您无法添加数组切片。而不是在中间拆分索引，这将永远不会让你交换相反的对（在基本情况下期望）。
如果你想象一下视觉上的递归，你可以看到它。您可以从以下列表开始：
1, 2, 3, 4
^ ^ <-- these need to swap in a reverse
但是在你的第一次递归调用后，你将其拆分为：
---- | ----
1, 2 3, 4
^ ^ <-- these still need to be swapped, bu when?
现在，分支1无法在分支2中的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]
我不知道你为什么要做递归。您可以简单地选择两个指针，一个在开头，一个在字符串的末尾，首先交换这些字符，然后将指针朝向彼此移动，直到它们交叉，然后断开并返回反转的字符串。
class Solution:
def reverseString(self, s):
if len(s) <= 1: return s
# The two pointers
lo = 0
hi = len(s) - 1
# Iterate till both pointers cross
while lo < hi:
# swap the characters
tmp = s[lo]
s[lo] = s[hi]
s[hi] = tmp
# increment the pointers
lo += 1
hi -= 1
return s
s = Solution()
print(s.reverseString(['h']))
print(s.reverseString(["h","e","l","l","o"]))
print(s.reverseString(["h","e","l","l","o","w","o","r","l","d"]))
#['h']
#['o', 'l', 'l', 'e', 'h']
#['d', 'l', 'r', 'o', 'w', 'o', 'l', 'l', 'e', 'h']
另外，相同的递归方法如下
class Solution:
def reverseString(self, s, lo=0, hi=None):
#If one character or less in the string, return the string
if len(s) <= 1:
return s
#The last index should be placed at the end of the string
if hi == None:
hi = len(s) - 1
#If the two indexes cross, return the string
if hi < lo:
return s
#swap the low and high characters
tmp = s[lo]
s[lo] = s[hi]
s[hi] = tmp
#Recursively call the function
return self.reverseString(s, lo + 1, hi - 1)
s = Solution()
print(s.reverseString(['h']))
print(s.reverseString(["h","e","l","l","o"]))
print(s.reverseString(["h","e","l","l","o","w","o","r","l","d"]))
#['h']
#['o', 'l', 'l', 'e', 'h']
['d', 'l', 'r', 'o', 'w', 'o', 'l', 'l', 'e', 'h']
这是针对此问题的解决方案：
class Solution(object):
def reverseString(self, s, left=0, right=0):
if right == 0:
right = len(s) - 1
if left >= right:
return
temp = s[right]
s[right] = s[left]
s[left] = temp
self.reverseString(s, left+1, right -1)