当前位置：首页 > article >正文

【字符串】——python反转字符串的7种方法

article 2024/12/29 8:22:28

344. 反转字符串

题目难度

简单

题目描述

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

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。

示例

示例 1

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

示例 2

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

提示信息

1 <= s.length <= 105
s[i]都是 ASCII 码表中的可打印字符。

解法一：双指针

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 定义左右指针
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

双指针概念：使用两个指针分别指向字符串的起始位置和结束位置，通过交换指针所指的元素来实现字符串的反转。这种方法在处理需要对数组或字符串进行两端操作的问题时非常常见。
Python 的同时赋值特性：s[left], s[right] = s[right], s[left]这种写法可以同时对两个变量进行赋值，无需借助中间变量。Python 会先计算等号右边的值，然后同时将值赋给等号左边的变量。在这个过程中，实际上是先创建了一个包含s[right]和s[left]的元组，然后将这个元组的值分别赋给s[left]和s[right]。

解法二：栈结构

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        原地修改，不用返回s，直接对s操作反转了！
        """
        stack = []        # 定义空栈stack[]
        for char in s:    # 从头遍历s中所有字符
            stack.append(char)  # 入栈用.append(xxx)实现
        # 实现了将s所有字符入栈，利用栈的结构特点 
        # 先入栈的后出栈，就实现了反转
        # for i in len(s):  len(s)是个数字，长度！for要for一个范围
        for i in range(len(s)):
            s[i] = stack.pop()  # i指定s[i]位置进行修改，.pop是出栈操作

栈的概念和操作：栈是一种数据结构，遵循后进先出（LIFO）的原则。在这个解法中，首先将字符串中的字符依次压入栈中，然后再从栈中弹出字符并覆盖原字符串的对应位置，实现反转。使用列表来模拟栈的操作，.append()方法用于将元素压入栈（列表末尾），.pop()方法用于弹出栈顶元素（列表末尾的元素）。
栈的结构特点:后进先出、先进后出正好适合做反转操作！

解法三：range函数

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        for i in range(n // 2):
            s[i], s[n - i - 1] = s[n - i - 1], s[i]

range函数的使用：range函数可以生成一个整数序列，例如range(n // 2)生成一个从0到字符串长度一半的整数序列，用于遍历字符串的前半部分。则i与n-1-i是对应的要交换的位置。
字符串长度的获取与索引操作：

解法四：reversed函数

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = reversed(s)

对这段代码中涉及的reversed函数和切片操作的详细解释：

一、reversed函数

作用：
- reversed是 Python 的内置函数，它接收一个可迭代对象作为参数，并返回一个反转后的迭代器。这个迭代器可以遍历输入可迭代对象的元素，但顺序是反转后的。
- 例如，对于列表[1, 2, 3]，reversed([1, 2, 3])会返回一个迭代器，当遍历这个迭代器时，会依次得到3、2、1。
特点：
- reversed函数不会直接修改原始的可迭代对象，而是返回一个新的迭代器。如果要获取反转后的具体内容，可以将其转换为列表、元组等具体的数据结构。
- 例如，list(reversed([1, 2, 3]))会得到[3, 2, 1]。

二、切片操作

基本概念：
- 在 Python 中，切片是一种用于从序列（如列表、字符串、元组等）中提取一部分元素的操作。它通过指定起始索引、结束索引和步长来定义要提取的部分。
- 切片的语法是sequence[start:stop:step]，其中start是起始索引（默认为 0），stop是结束索引（不包括该索引处的元素），step是步长（默认为 1）。
- 例如，对于列表my_list = [0, 1, 2, 3, 4, 5]，my_list[1:4]会得到[1, 2, 3]。
在代码中的作用：
- s[:]是一种特殊的切片操作，表示对整个序列s进行切片。这里的作用是将reversed(s)返回的反转后的迭代器转换为列表（或其他可迭代对象，具体取决于s的类型），并将其赋值给s，从而实现原地修改s。
- 相当于用反转后的内容替换了原始序列中的所有元素，达到了反转字符串（或列表等）的目的。

为什么代码这样写

首先，reversed(s)返回一个反转后的迭代器，这个迭代器包含了s中元素的反转顺序。
然后，通过s[:] = reversed(s)，将这个反转后的迭代器转换为具体的数据结构（通常是列表），并将其赋值给s的整个切片。这样做的好处是可以原地修改s，而不需要创建一个新的列表来存储反转后的结果，从而节省了内存空间。
同时，这种写法简洁明了，利用了 Python 的内置函数和切片操作的强大功能，以一种高效的方式实现了字符串（或列表等）的反转。

解法五：切片

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = s[::-1]

让我们来通俗地理解这段代码涉及的知识点。

一、字符串切片

想象字符串就像一串漂亮的珠子，每个珠子代表一个字符。字符串切片就像是从这串珠子中选取一部分珠子的工具。

正常的切片，比如s[start:end:step]：
- start是你开始选取珠子的位置。
- end是你停止选取珠子的位置（但不包括这个位置上的珠子）。
- step是你每次选取珠子的间隔。
- 例如s[2:5]，就像是从这串珠子的第三个位置开始，一直拿到第五个位置之前的珠子。
特殊的切片s[::-1]：
- 这里没有指定开始和结束位置，意味着从字符串的开头一直取到结尾。
- 步长为-1，就像是你从字符串的末尾开始，每次向前走一步，依次选取珠子，一直走到字符串的开头。所以这样就得到了一个反转后的字符串。

二、赋值给s[:]

现在想象s是一个装着珠子的盒子。s[:]表示整个盒子里的所有珠子。把s[::-1]赋值给s[:]，就像是把用特殊切片方法得到的反转后的那串珠子，全部替换掉原来盒子里的珠子。这样就实现了在不创建新盒子（不占用额外空间）的情况下，把原来盒子里的珠子顺序反转了。

所以这段代码的作用就是通过巧妙地利用字符串切片和赋值操作，原地反转了给定的字符串（实际上是字符列表）。

知识要点：
- 字符串切片的高级用法：切片操作s[::-1]表示从字符串末尾开始，每次向前移动一步，直到字符串开头，从而得到反转后的字符串。这种切片语法非常强大，可以用于快速提取字符串的一部分、跳过特定元素等。在这里，通过将切片结果赋值给s[:]，实现了原地反转字符串。

解法六：列表推导

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = [s[i] for i in range(len(s) - 1, -1, -1)]

知识要点：
- 列表推导式的原理：列表推导式是一种简洁的语法，用于快速生成列表。在这个解法中，[s[i] for i in range(len(s) - 1, -1, -1)]生成一个从字符串末尾到开头的字符列表。通过遍历从字符串长度减 1 到 0 的索引，将每个字符添加到列表中。然后通过切片赋值将这个列表覆盖原字符串，实现反转。
- 索引的反向遍历：range(len(s) - 1, -1, -1)表示从字符串长度减 1 开始，每次递减 1，直到 -1（不包括 -1），实现了对字符串索引的反向遍历。

以下是对这种解法思路的详细解释，包括涉及的语法知识：

一、列表推导式的原理

基本概念：
- 列表推导式是一种简洁的语法，用于快速生成新的列表。它的基本形式是[expression for item in iterable if condition]，其中expression是对每个item进行的操作，iterable是一个可迭代对象，if condition是可选的过滤条件。
- 例如，[i * 2 for i in range(5)]会生成一个包含0, 2, 4, 6, 8的列表。这里对range(5)生成的每个整数进行了乘以 2 的操作。
在本题中的应用：
- [s[i] for i in range(len(s) - 1, -1, -1)]这个列表推导式的目的是生成一个反转后的字符列表。
- s[i]表示取原始字符串s中索引为i的字符。
- range(len(s) - 1, -1, -1)是一个整数序列，从字符串的最后一个索引开始，依次递减到第一个索引（不包括 -1）。这样就实现了对字符串索引的反向遍历。

二、索引的反向遍历

range函数的参数解释：
- range(len(s) - 1, -1, -1)中，len(s) - 1是起始值，表示字符串的最后一个索引。
- -1是结束值，表示要遍历到索引为 0 的前一个位置，因为索引是从 0 开始的，所以不包括 -1 这个位置。
- 最后一个 -1是步长，表示每次递减 1。
反向遍历的作用：
- 通过这种反向遍历，可以依次取到字符串中的每个字符，从最后一个字符开始，到第一个字符结束。这样就可以构建一个反转后的字符列表。

三、切片赋值实现反转

s[:]的作用：
- s[:]表示对整个字符串（实际上是字符列表）进行切片操作。这里的作用是将新生成的反转后的字符列表覆盖到原始字符串上，实现原地反转。
- 相当于把原来的字符串用新生成的反转后的字符列表替换掉。

这种解法的设计思路是利用列表推导式快速生成反转后的字符列表，然后通过切片赋值将其覆盖到原始字符串上，从而实现不使用额外空间的字符串反转。这种方法展示了 Python 语言中列表推导式和切片操作的灵活性和强大功能。

解法七：reverse()函数

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s_list = list(s)
        s_list.reverse()
        s[:] = s_list

知识要点：
- 列表的 reverse 方法：列表有一个reverse方法，可以原地反转列表。在这个解法中，首先将输入字符串转换为列表s_list，然后调用s_list.reverse()原地反转列表。最后，将反转后的列表转换回字符串，并通过切片赋值覆盖原字符串，实现反转。
- 类型转换：list(s)将字符串转换为列表，这样就可以使用列表的方法进行操作。然后，将反转后的列表转换回字符串时，通过切片赋值s[:] = s_list实现原地修改字符串。

综上所述，这些解法展示了 Python 中多种不同的编程技巧和数据结构的用法，通过巧妙地利用这些知识，可以高效地解决字符串反转问题。

补充：
元组：
在Python中，元组（Tuple）是一种不可变的有序序列，它与列表类似，但有一些重要的区别。以下是关于元组的详细介绍：

元组的定义

元组使用小括号()来表示，其中的元素用逗号分隔。例如：my_tuple = (1, 2, 3)定义了一个包含三个整数元素的元组。
元组也可以不使用小括号，直接用逗号分隔元素来定义，例如：my_tuple = 1, 2, 3与上面的定义是等价的。

元组的特点

不可变性：元组一旦创建，其元素就不能被修改、删除或替换。这意味着元组提供了一种数据完整性的保证，适合用于存储不应该被改变的数据集合。
有序性：元组中的元素是有序的，可以通过索引来访问。与列表一样，元组的索引从0开始，例如my_tuple[0]将访问元组中的第一个元素。

在同时赋值中的作用

在 s[left], s[right] = s[right], s[left]这种同时赋值的语句中，等号右边的s[right], s[left]实际上构成了一个临时的元组。Python会先计算这个元组的值，即获取s[right]和s[left]的值，并将它们组合成一个元组(s[right]的值, s[left]的值)。
然后，Python会将这个元组中的元素按照顺序分别赋给等号左边的变量s[left]和s[right]。这种方式简洁地实现了两个变量值的交换，而无需使用中间变量来临时存储值。

为什么使用元组概念

简洁性：使用元组可以在一行代码中完成多个变量的赋值操作，使代码更加简洁和易读。相比于使用中间变量来实现交换，这种方式更加直观和高效。
原子性：元组的不可变性保证了在赋值过程中的原子性。即整个赋值操作是一个不可分割的整体，要么全部成功，要么全部失败。不会出现中间状态，从而避免了一些潜在的错误和不一致性。
与Python语法的一致性：Python的语法设计中广泛使用了元组和类似元组的结构。例如，函数可以返回多个值，实际上返回的就是一个元组。在很多其他的场景中，元组也被用于表示一组相关的值。因此，在同时赋值中使用元组概念与Python的整体语法风格和编程习惯是一致的。

元组在Python中有多种应用场景，以下是一些常见的例子：

数据打包与解包

多值返回：函数可以返回多个值，这些值会被自动打包成一个元组。例如：

def get_name_and_age():
    return "Alice", 25

name, age = get_name_and_age()
print(name)  
print(age)

在这个例子中，get_name_and_age函数返回了一个包含姓名和年龄的元组，然后通过多变量赋值将元组中的值分别赋给了name和age变量。

数据交换：如前面提到的交换变量的值，使用元组可以在不借助中间变量的情况下简洁地实现交换操作。

a = 5
b = 10
a, b = b, a
print(a)  
print(b)

函数参数传递

固定参数顺序：当函数需要接收多个参数，且这些参数的顺序和含义是固定的时，可以使用元组来传递参数。例如，对于一个绘制图形的函数，可能需要接收坐标点的元组作为参数。

def draw_point(point):
    x, y = point
    print(f"绘制点 ({x}, {y})")

point = (3, 4)
draw_point(point)

可变参数：在函数定义中，可以使用元组来接收不确定数量的参数。通过在参数前加上*，可以将多个参数收集到一个元组中。

def print_args(*args):
    for arg in args:
        print(arg)

print_args(1, 2, 3, "hello")

数据保护与不可变性

防止数据意外修改：当需要确保数据不被修改时，元组是一个很好的选择。例如，配置信息、常量数据等可以使用元组来存储，以防止在程序的其他部分意外地修改这些数据。

COLORS = ('red', 'green', 'blue')
# 以下代码会引发错误，因为元组是不可变的
# COLORS[0] = 'yellow'

数据结构中的元素

字典的键：元组可以作为字典的键，因为它是不可变的。这在需要使用多个值作为字典键的情况下非常有用。

student_info = {('Alice', 25): '优秀', ('Bob', 22): '良好'}
print(student_info[('Alice', 25)])

集合的元素：元组也可以作为集合的元素，同样是因为其不可变性。集合中的元素必须是唯一的，使用元组作为元素可以方便地存储和操作多个相关的值。

my_set = {(1, 2), (3, 4), (1, 2)}
print(my_set)

并行迭代

可以同时迭代多个可迭代对象，将它们的元素组合成元组进行处理。例如，同时遍历两个列表并打印对应的元素。

names = ["Alice", "Bob", "Charlie"]
ages = [25, 30, 35]
for name, age in zip(names, ages):
    print(f"{name} is {age} years old.")

数据库操作

在与数据库交互时，查询结果通常以元组的形式返回。每个元组代表一行数据，其中的元素对应于查询结果中的列。

import sqlite3

conn = sqlite3.connect('example.db')
cursor = conn.cursor()
cursor.execute("SELECT name, age FROM students")
results = cursor.fetchall()
for row in results:
    print(row)  
conn.close()

这些只是元组在Python中的一些常见应用场景，实际上，元组在各种不同的编程任务和数据处理场景中都有广泛的应用，它的不可变性和简洁性使其成为Python编程中一个非常有用的数据结构。

以下是对range函数的详细介绍：

一、range函数的特点

生成整数序列：
- range函数主要用于生成一个整数序列。它可以接受一个、两个或三个参数，分别对应不同的用法。
- 当只传入一个参数n时，range(n)会生成从0到n - 1的整数序列。例如，range(5)会生成0, 1, 2, 3, 4。
- 当传入两个参数start和end时，range(start, end)会生成从start到end - 1的整数序列。例如，range(2, 5)会生成2, 3, 4。
- 当传入三个参数start、end和step时，range(start, end, step)会生成从start开始，每次增加step，直到小于end的整数序列。例如，range(1, 10, 2)会生成1, 3, 5, 7, 9。
高效性：
- range对象是一种“惰性求值”的序列类型，它不会一次性生成所有的整数，而是在需要的时候逐个生成。这使得它在处理大量整数序列时非常高效，尤其是在内存受限的情况下。
可迭代性：
- range对象是可迭代的，可以在for循环中直接使用。例如：for i in range(5): print(i)会依次打印0, 1, 2, 3, 4。

二、range函数的使用方式

基本用法：
- 如前面提到的，用于生成整数序列，并在for循环中进行遍历。
- 例如：for i in range(3): print(f"第 {i + 1} 次循环")。
结合列表推导式：
- 可以与列表推导式结合使用，快速生成列表。例如：new_list = [i * 2 for i in range(5)]会生成一个包含0, 2, 4, 6, 8的列表。
作为函数参数：
- 一些函数接受可迭代对象作为参数，range生成的整数序列可以作为这些函数的参数。例如，sum(range(1, 11))可以计算从 1 到 10 的整数之和。

三、range函数的应用场景

循环控制：
- 在需要进行固定次数循环的情况下，range非常有用。例如，遍历一个列表并对每个元素进行处理。
- 例如：my_list = [1, 2, 3, 4, 5]，for i in range(len(my_list)):可以遍历列表的索引，从而访问和修改列表中的元素。
生成索引序列：
- 在需要对序列进行索引操作时，可以使用range生成索引序列。例如，在字符串反转的例子中，通过range(n // 2)生成字符串前半部分的索引序列，用于交换字符。
步长控制：
- 当需要按照特定的步长进行遍历或生成序列时，可以使用第三个参数指定步长。例如，生成奇数序列可以使用range(1, 10, 2)。
与其他数据结构结合：
- 可以与列表、元组、集合等数据结构结合使用，进行各种操作。例如，生成一个包含特定范围内整数的列表，或者对一个可迭代对象进行切片操作时，可以使用range来确定切片的起始和结束位置。

总之，range函数是 Python 中非常实用的一个工具，它在循环控制、索引操作、生成序列等方面有广泛的应用，可以提高代码的效率和可读性。

时空复杂度分析

以下是对这七种解法的时间复杂度和空间复杂度分析以及对比：

一、解法一：双指针

时间复杂度：
- 由于只需要一次遍历字符串的一半长度，所以时间复杂度为 $O (n)$ ，其中 n 是字符串的长度。
空间复杂度：
- 只使用了两个指针变量，没有额外的数据结构，所以空间复杂度为 $O (1)$ 。

二、解法二：栈结构

时间复杂度：
- 遍历一次字符串将字符入栈，再遍历一次字符串出栈并赋值，总共遍历两次字符串，时间复杂度为 $O (n)$ 。
空间复杂度：
- 使用了一个栈来存储字符串中的字符，最坏情况下需要存储整个字符串，所以空间复杂度为 $O (n)$ 。

三、解法三：range 函数

时间复杂度：
- 同样是遍历字符串的一半长度进行交换操作，时间复杂度为 $O (n)$ 。
空间复杂度：
- 没有使用额外的数据结构，只使用了几个变量，空间复杂度为 $O (1)$ 。

四、解法四：reversed 函数和切片

时间复杂度：
- 创建反转迭代器和进行切片赋值的操作时间复杂度为 $O (n)$ 。
空间复杂度：
- reversed函数返回的迭代器不占用额外空间，切片赋值是原地操作，空间复杂度为 $O (1)$ 。

五、解法五：切片

时间复杂度：
- 切片操作本身的时间复杂度可以认为是 $O (n)$ ，因为它涉及到遍历字符串。
空间复杂度：
- 切片操作是原地修改，没有额外的数据结构，空间复杂度为 $O (1)$ 。

六、解法六：列表推导

时间复杂度：
- 列表推导式遍历字符串的时间复杂度为 $O (n)$ ，再加上切片赋值的时间复杂度为 $O (n)$ ，总体时间复杂度为 $O (n)$ 。
空间复杂度：
- 列表推导式创建了一个新的临时列表，最坏情况下长度为 n，但最后通过切片赋值覆盖原列表，所以空间复杂度为 $O (n)$ （临时列表占用空间）和 $O (1)$ （最终的空间复杂度）的混合，考虑到最终原地修改，整体可以认为是 $O (1)$ 。

七、解法七：reverse()函数

时间复杂度：
- 列表的 reverse 方法时间复杂度为 $O (n)$ 。
空间复杂度：
- 创建了一个新的列表，然后再进行切片赋值，临时列表占用空间为 $O (n)$ ，但最终原地修改，整体空间复杂度可以认为是 $O (1)$ 。

对比分析：

时间复杂度：七种解法的时间复杂度都是 $O (n)$ ，差别不大。但是在实际运行中，由于操作的不同，可能会有一些细微的性能差异。例如，双指针、range 函数、reversed 函数和切片等方法相对较为简洁直接，可能在某些情况下执行速度稍快。
空间复杂度：解法一、三、四、五、七的空间复杂度都是 $O (1)$ ，因为它们都是原地修改，没有使用额外的线性空间。解法二使用了栈，最坏情况下空间复杂度为 $O (n)$ 。解法六在列表推导过程中创建了临时列表，虽然最终也是原地修改，但在过程中可能占用额外空间，整体也可以认为是 $O (1)$ 。