Java：能否以O(1)空间、O(n)时间反转字符串？面试疑问解析

Great question—you’re totally right to pick up on the trap here with Java’s immutable String type! Let’s break this down clearly:

核心前提：Java的String不可变性 #

First, let’s confirm: Java’s String is immutable, meaning you can’t modify individual characters in an existing String object. Any "modification" (like reversing) will always create a new String instance, which inherently requires O(n) space to store the reversed characters. That’s why this feels like a trap question.

可行的场景：操作char数组 #

If the problem allows working with a char[] instead of a strict String input/output (or if you’re allowed to convert the String to a char[] for the reversal step), then you absolutely can achieve O(1) extra space and O(n) time with a two-pointer approach:

实现代码 #

public static void reverseCharArray(char[] chars) {
    int left = 0;
    int right = chars.length - 1;
    
    while (left < right) {
        // Swap the characters at left and right pointers
        char temp = chars[left];
        chars[left] = chars[right];
        chars[right] = temp;
        
        left++;
        right--;
    }
}

为什么这符合要求？ #

• Time complexity: O(n) — we iterate through half the array, swapping each pair of characters exactly once.
• Space complexity: O(1) — we only use three extra variables (left, right, temp) regardless of the input size. No additional arrays or objects are created.

If you need to convert back to a String afterward, you’d do new String(chars), but this step creates a new String with O(n) space. However, the reversal operation itself uses O(1) extra space.

不可行的场景：严格返回String且O(1)额外空间 #

If the problem strictly requires starting and ending with a String and using zero additional O(n) space, then it’s impossible. Here’s why:

• Even using StringBuilder (which is mutable) requires an underlying char[] to store the reversed characters, which takes O(n) space.
• Any method that returns a reversed String must create a new String object, which holds a copy of all reversed characters — that’s unavoidable O(n) space.

总结 #

• If the problem allows working with char[] (or counts the input conversion as part of the problem’s setup), O(1) space + O(n) time is achievable with the two-pointer method.
• If the problem strictly requires String input/output with no O(n) extra space, it’s a trick question — Java’s immutable String makes this impossible.

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