字符串单词反转：时间与空间复杂度最优方案选方法1还是方法2？

一、最优实现方案 #

要实现时间与空间复杂度最优的字符串单词反转（每个单词内部字符反转，单词顺序保持不变），原地字符数组处理是最优选择，具体思路如下：

1. 将字符串转为字符数组（规避String不可变特性带来的额外开销）；
2. 遍历数组，定位每个单词的起始与结束索引；
3. 对每个单词的字符区间进行原地反转；
4. 最后将字符数组转回字符串（或直接输出结果）。

该方案的时间复杂度为O(n)（n为字符串总长度，每个字符仅被访问和交换常数次），空间复杂度为O(1)（仅使用固定数量的临时变量；若输入为不可变字符串，仅需O(n)空间存储字符数组，这是处理字符串的必要开销）。

示例代码（Java）：

public static String reverseWords(String s) {
    char[] arr = s.toCharArray();
    int n = arr.length;
    int start = 0;
    for (int end = 0; end <= n; end++) {
        if (end == n || arr[end] == ' ') {
            reverse(arr, start, end - 1);
            start = end + 1;
        }
    }
    return new String(arr);
}

private static void reverse(char[] arr, int left, int right) {
    while (left < right) {
        char temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

二、两种给定方法的复杂度对比 #

方法1（栈实现） #

Stack<Character> st = new Stack<Character>();
for (int i = 0; i < str.length(); ++i) {
    if (str.charAt(i) != ' ')
        st.push(str.charAt(i));
    else {
        while (st.empty() == false) {
            System.out.print(st.pop());
        }
        System.out.print(" ");
    }
}
while (st.empty() == false) {
    System.out.print(st.pop());
}

• 时间复杂度：O(n)。每个字符入栈、出栈各一次，总操作数为2n，属于线性时间开销。
• 空间复杂度：O(k)。k为字符串中最长单词的长度，栈最多存储一个单词的所有字符，空间消耗远小于整个字符串长度。

方法2（split+字符串拼接） #

String welcomeString = "Welcome to Zscaler";
String removeSpace[] = welcomeString.split(" ");
String reversedString = "";
for (int i = 0; i < removeSpace.length; i++) {
    String getString = removeSpace[i];
    reversedString = "";
    for (int j = getString.length() - 1; j >= 0; j--) {
        reversedString = reversedString + getString.charAt(j);
    }
    System.out.print(reversedString + " ");
}

• 时间复杂度：O(n²)。Java中String是不可变对象，每次reversedString = reversedString + ...都会创建新的String对象，复制已有字符再添加新字符，单个单词反转的时间复杂度为O(m²)（m为单词长度），总时间随字符串长度呈平方级增长。
• 空间复杂度：O(n)。split方法会创建数组存储所有单词，每次拼接字符串也会生成多个临时String对象，总空间消耗等于甚至超过整个字符串的长度。

结论 #

从时间和空间复杂度维度看，方法1的性能远优于方法2。方法1是线性时间+低空间开销，而方法2是平方级时间+高空间开销，处理长字符串时性能差异会非常明显。

内容的提问来源于stack exchange，提问作者Akshay Hukire