首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >反转字符串的就地递归解决方案

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

Stack Overflow用户
提问于 2019-04-17 07:36:07
回答 7查看 3K关注 0票数 1

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

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

编写一个反转字符串的函数。输入字符串以字符数组char[]的形式给出。

不要为另一个数组分配额外的空间,您必须通过使用O(1)额外内存就地修改输入数组来实现这一点。

您可以假设所有字符都由printable ascii characters组成。

示例1:

输入:"h","e","l","l","o“输出:"o","l","l","e","h”

示例2:

输入:"H","a","n","n","a","h“输出:"h","a","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,递归切分字符串的开销很大。

作为改进的第一步,引入了参数lohi来存储索引

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               

It报告错误

RecursionError:在比较中超出了最大递归深度

在0.005s内运行了1个测试

有什么问题吗?

EN

回答 7

Stack Overflow用户

发布于 2019-04-17 08:12:10

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

如果你在视觉上想象一下递归,你可以看到它。您可以从如下列表开始:

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]
票数 3
EN

Stack Overflow用户

发布于 2019-04-17 07:45:21

我不确定你为什么要做递归。您可以简单地获取两个指针,一个在字符串的开头,另一个在字符串的结尾,首先交换这些字符,然后将指针相互移动,直到它们交叉,然后断开并返回相反的字符串。

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']
票数 1
EN

Stack Overflow用户

发布于 2019-05-28 13:58:43

下面是这个问题的解决方案:

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)
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/55717930

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档