python经典百题之字符反转

题目:字符串反转，如将字符串 “www.runoob.com” 反转为 “moc.boonur.www”?

程序分析

要实现字符串的反转，可以考虑以下方法：

1. 逆序切片：利用切片特性，步长为-1，将字符串逆序。
2. 逐字符反转：遍历字符串，将字符逐个添加到新字符串的开头，实现反转。
3. 栈：利用栈数据结构，先将字符串中的字符依次入栈，然后再依次出栈，得到反转后的字符串。

方法一：逆序切片

解题思路

利用切片特性，设置步长为-1，实现字符串的逆序。

代码实现

def reverse_string_slice(s):
    return s[::-1]
1
2

优缺点

• 优点：简单，代码简洁。
• 缺点：生成了新的字符串，空间复杂度为O(n)，其中n是字符串长度。

方法二：逐字符反转

解题思路

遍历原字符串，将每个字符依次添加到新字符串的开头，实现反转。

代码实现

def reverse_string_character(s):
    reversed_str = ""
    for char in s:
        reversed_str = char + reversed_str
    return reversed_str
1
2
3
4
5

优缺点

• 优点：不使用额外空间，空间复杂度为O(1)。
• 缺点：时间复杂度较高，为O(n^2)，其中n是字符串长度。

方法三：栈

解题思路

使用栈的先进后出特性，将字符串中的字符依次入栈，然后再依次出栈，得到反转后的字符串。

代码实现

def reverse_string_stack(s):
    stack = []
    for char in s:
        stack.append(char)
    
    reversed_str = ""
    while stack:
        reversed_str += stack.pop()
    
    return reversed_str
1
2
3
4
5
6
7
8
9
10

优缺点

• 优点：时间复杂度较低，为O(n)，空间复杂度也为O(n)，其中n是字符串长度。
• 缺点：需要额外的空间来存储栈。

总结与推荐

• 方法三（栈）是推荐的最佳方法，因为它具有较高的效率和合理的空间复杂度，同时不会产生额外的空间复杂度。时间复杂度为O(n)，空间复杂度为O(n)。
• 方法二（逐字符反转）虽然不需要额外空间，但时间复杂度较高，不推荐在实际应用中使用。
• 方法一（逆序切片）简单直接，但会生成新的字符串，产生额外空间复杂度。在不需要考虑空间复杂度的情况下可以使用。