我正在从 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 有什么问题吗?
最佳答案
要在没有空间的情况下执行此操作,您需要交换。您不能添加数组切片。而不是在中间拆分索引,这永远不会让您交换相反的对(在基本情况下除外)。
如果您直观地想象递归,就可以看到它。你从一个像这样的列表开始:
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]
关于python - 反转字符串的就地递归解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55717930/