算法@LeetCode:Reverse String

Log

• 【170808】完成 01 版 Python 提交
• 【170808】完成 02 版 Python 提交
• 【170808】完成 03 版 Python 提交
• 【170808】查看最优解法（Python）并自行实现了一遍

题目

Reverse String

【题目类型备注】

双指针，字符串

提交

01

【语言】

Python

【时间】

170808

【思路】

本次提交前，没有查看 Related Topics，仅仅是通过搜索 String 而找到的。我本次提交的两种代码版本思路是一致的：读取字符串每一位，从头读到尾，每读取一位就保存一位，最后反向输出即可。区别在于：通过的代码通过了一个「栈」+字符串 join 方法来实现，并且是先读取，保存，最后连接而实现，试验若干次，从未超时 TLE；没通过的代码则是每读取一个就反向连接一次，结果尝试了若干次，都超时 TLE。超时代码如下：

class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        ans = ""
        maxlen = len(s)
        if maxlen <= 1:
            return s
        
        for i in range(maxlen-1, -1, -1):
            ans += s[i]
        
        return ans

【代码】

class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stk = []
        for i in s:
            stk.append(i)
 
        ans = []
        while(len(stk) > 0):
            ans.append(stk.pop())
 
        return ''.join(ans)

【结果】

运行时：85 ms

报告链接：https://leetcode.com/submissions/detail/113009678/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 5.23 % of python submissions.

02

【语言】

Python

【时间】

170808

【思路】

看到了双指针，我联想到了快排，然后就想到了递归。于是写了一个递归版本。当然试验显示，递归版本更慢点。

【代码】

class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) in [0, 1]:
            return s
        if len(s) == 2:
            return s[-1]+s[0]
        if len(s) >= 3:
            mid = len(s)//2
            return self.reverseString(s[(mid+1):]) + s[mid] + self.reverseString(s[:mid])

【结果】

运行时：105 ms

报告链接：https://leetcode.com/submissions/detail/113011390/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 3.36 % of python submissions.

03

【语言】

Python

【时间】

170808

【思路】

想到 Python 里好像有一个函数能把字符串转为字符数组，查了一下果然有：直接 list(str) 即可。然后我又记得列表有一个 .reverse() 方法，于是就改写了这个代码。一改，经过多次测试，发现速度好快……

【代码】

class Solution(object):
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) >= 1:
            rev = list(s)
            rev.reverse()
            return ''.join(rev)
        else:
            return s

【结果】

运行时：42 ms

报告链接：https://leetcode.com/submissions/detail/113013390/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 65.99 % of python submissions.

00

参考解法：

• Python
  • 其中 Pythonic 的写法用了 Extended Slices。剩下的两种解法中，递归的自己实现过；而双指针的写法，有想到，但以为这样的复杂度估计也是 O(n) 级别的，剩了常数倍（一半）的时间，感觉可能还有更快的解法，就没写。扫视了 Java 和 C++ 的推荐答案后，都没有发现更优的解法。或许就是用这种方法吧。

自己实现一遍最优解：

• Python