【LeetCode 344.反转字符串】四种解法（内置方法/切片/双指针/递归）超详细解析（Python3完整代码）

ZengShaonan

599人浏览 · 2026-03-08 12:40:16

ZengShaonan · 2026-03-08 12:40:16 发布

一、题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

题目要求

不要给另外的数组分配额外的空间，必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题；
元素的类型为 str，函数无返回值（None）。

示例

输入：s = ["h","e","l","l","o"]

输出：无返回值，s 被修改为 ["o","l","l","e","h"]

输入：s = ["H","a","n","n","a","h"]

输出：无返回值，s 被修改为 ["h","a","n","n","a","H"]

二、解法一：Python内置reverse()方法

1. 思路分析

Python列表内置了reverse()方法，可直接原地反转列表，完全符合题目“原地修改、O(1)空间”的要求，是日常开发/刷题中最简洁的解法。

2. 完整代码

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 直接调用列表内置的reverse方法，原地反转列表
        s.reverse()

3. 代码解析

s.reverse()：列表的内置方法，直接修改原列表（无返回值），底层实现为双指针交换，时间和空间复杂度均为最优；
执行示例：输入 ["h","e","l","l","o"] → 执行后 s 直接变为 ["o","l","l","e","h"]。

4. 复杂度分析

时间复杂度：O(n)，需遍历列表一次完成所有元素的反转；
空间复杂度：O(1)，原地修改列表，无额外空间占用。

5. 优缺点

优点：代码极简，一行解决问题，符合Pythonic风格。
缺点：依赖语言内置方法，无法体现算法核心思想

三、解法二：切片操作（简洁但需注意“原地”）

1. 思路分析

Python的切片语法 s[::-1] 可生成反转后的新列表，但直接赋值 s = s[::-1] 会创建新列表（仅修改变量引用，原数组未变，不符合“原地修改”要求）；需用 s[:] = s[::-1] 实现原地替换原列表的所有元素。

2. 完整代码

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 关键：s[:] 表示替换原列表的所有元素，实现原地修改
        s[:] = s[::-1]

3. 核心解析（切片写法对比）

写法	执行效果	是否符合“原地修改”要求
`s = s[::-1]`	创建反转后的新列表，仅修改变量`s`的引用	原数组内存地址未变，内容未修改
`s[:] = s[::-1]`	把反转后的元素逐个替换到原列表的内存空间中	直接修改原数组内容

4. 复杂度分析

时间复杂度：O(n)，切片需遍历列表生成反转后的新列表，再将新列表元素替换到原列表；
空间复杂度：O(n)，切片会生成一个临时的反转列表，占用O(n)额外空间，不符合题目“O(1)空间”的核心要求，仅作为拓展解法。

5. 优缺点

优点：代码简洁，仅一行，比双指针写法更短
缺点：空间复杂度不满足题目要求，依赖Python切片特性，跨语言无法复用

四、解法三：双指针法（基础最优解）

1. 思路分析

双指针是反转类问题的通用经典解法（无语言依赖），核心逻辑：

初始化左指针 l（指向列表头部，索引0）、右指针 r（指向列表尾部，索引len(s)-1）；
交换 s[l] 和 s[r] 的值；
左指针右移（l += 1），右指针左移（r -= 1）；
重复步骤2-3，直到 l >= r（指针相遇/交叉，无需继续交换）。

2. 完整代码

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 初始化左右指针
        left, right = 0, len(s) - 1
        # 指针未交叉时循环（l < r 而非 l <= r，避免中间元素重复交换）
        while left < right:
            # 交换左右指针指向的元素（Python无需临时变量，直接解包交换）
            s[left], s[right] = s[right], s[left]
            # 移动指针
            left += 1
            right -= 1

3. 执行过程（以示例 `s = ["h","e","l","l","o"]` 为例）

循环次数	left	right	交换前s	交换后s	指针移动
1	0	4	[“h”,“e”,“l”,“l”,“o”]	[“o”,“e”,“l”,“l”,“h”]	left=1, right=3
2	1	3	[“o”,“e”,“l”,“l”,“h”]	[“o”,“l”,“l”,“e”,“h”]	left=2, right=2
结束	2	2	-	-	循环终止

4. 复杂度分析

时间复杂度：O(n)，最多循环 $\frac{n}{2}$ 次（n为列表长度），每个循环仅做常数次操作；
空间复杂度：O(1)，仅使用两个指针变量，完全符合题目“原地修改、O(1)空间”的核心要求。

5. 优缺点

优点：
        1. 无语言依赖，通用最优解；
        2. 空间复杂度严格O(1)；
缺点 :
        代码量略多于内置方法/切片。

五、解法四：递归法（理解递归思想）

1. 思路分析

递归的核心是“分治+终止条件”：将“反转整个列表”的问题，分解为“交换首尾元素 + 反转中间子列表”，直到子列表长度≤1（递归终止）。

2. 完整代码

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 调用递归函数，初始左右指针为列表首尾
        self.recursion(s, 0, len(s) - 1)
    
    # 递归函数：反转s[left...right]区间内的元素
    def recursion(self, s: List[str], left: int, right: int) -> None:
        # 递归终止条件：左指针 >= 右指针（子列表无元素/仅一个元素）
        if left >= right:
            return
        # 先递归反转中间子列表（left+1 到 right-1）
        self.recursion(s, left + 1, right - 1)
        # 再交换当前首尾元素
        s[left], s[right] = s[right], s[left]

3. 递归执行过程（以 `s = ["h","e","l","l","o"]` 为例）

reverseString(s) → 调用 recursion(s, 0, 4)

        recursion(s, 0, 4) → 调用 recursion(s, 1, 3)

                recursion(s, 1, 3) → 调用 recursion(s, 2, 2)

                        recursion(s, 2, 2) → left >= right，直接返回

                交换 s[1] 和 s[3] → s = ["h","l","l","e","o"]

        交换 s[0] 和 s[4] → s = ["o","l","l","e","h"]

4. 复杂度分析

时间复杂度：O(n)，每个元素仅被交换一次，递归调用次数为 $\frac{n}{2 }$ ；
空间复杂度：O(n)：递归调用会占用系统栈空间，栈的深度为 $\frac{n}{2 }$ ，不符合题目“O(1)空间”要求，仅用于算法思想学习。

5. 优缺点

优点：

        锻炼递归思维，理解“分治”思想
缺点：
        1.空间复杂度高；
        2. 递归深度过大时可能触发栈溢出；
        3. 实际开发中效率低于双指针

六、总结

1. 核心要点

题目核心要求：原地修改 + O(1)空间，双指针法和内置reverse()方法是最优解；
切片写法需注意：s[:] = s[::-1] 才是原地修改，s = s[::-1] 不符合要求；
双指针循环条件：用 left < right 而非 left <= right，避免中间元素重复交换。

2. 解法选择建议

场景	推荐解法	原因
日常刷题/快速解题	内置reverse()方法	代码极简，一行解决
面试/算法学习	双指针法	通用、无语言依赖，体现算法思想
拓展思路/学习递归	递归法	理解分治和递归终止条件
仅作语法拓展	切片法	需注意空间复杂度问题