字符串反转算法解析：实现单词反转的多种方法

在编程中，字符串操作是基础且重要的部分。单词反转（Word Reversal）是指将一个句子中的每个单词顺序颠倒，例如将 "Hello World" 反转为 "World Hello"。本文将介绍几种常见的实现方法，并分析其时间复杂度和适用场景。

方法一：整体反转 + 局部反转

这是最经典的解法。步骤：1. 将整个字符串反转；2. 再对每个单词局部反转。例如：
输入: "Hello World"
整体反转: "dlroW olleH"
局部反转单词: "World Hello"
这种方法需要 O(n) 空间（如果字符串不可变）或 O(1) 空间（原地操作），时间复杂度 O(n)。

方法二：使用栈

遍历字符串，将单词依次推入栈中，然后依次弹出即可得到反转后的顺序。这种方法简单直观，但需要额外的栈空间。

方法三：利用 split 和 join

大多数高级语言（如 Python、Java）提供了字符串分割和拼接方法：
s = 'Hello World'
words = s.split()
reversed_words = ' '.join(reversed(words))
这种方法代码简洁，适合快速开发，但需要额外存储分割后的单词列表。

方法四：双指针技巧

在不使用额外存储的情况下，可以通过双指针进行原地反转。例如在字符数组中，先整体反转，然后使用两个指针分别指向每个单词的起始和结束进行局部反转。

性能比较

在选择方法时，需考虑语言特性、性能要求和代码可读性。

Python 示例代码

def reverse_words(s):
    # 方法1：整体+局部
    s_list = list(s)
    # 整体反转
    s_list.reverse()
    start = 0
    for i in range(len(s_list)):
        if s_list[i] == ' ':
            s_list[start:i] = reversed(s_list[start:i])
            start = i + 1
    # 反转最后一个单词
    s_list[start:] = reversed(s_list[start:])
    return ''.join(s_list)

print(reverse_words("Hello World"))  # 输出 "World Hello"

总结

单词反转问题看似简单，但涵盖了许多基本编程概念。根据实际需求选择合适的算法，能提升程序效率与可维护性。希望本文能帮助你更好地理解字符串操作的精髓。