如何修改该回文检测Java程序以实现O(n)时间复杂度？

我的程序当前仅用于检测字符串是否为回文，并根据检测结果输出对应提示信息。现有程序代码如下：

class ChkPalindrome { 
public static void main(String args[]) { 
String str, rev = ""; 
Scanner sc = new Scanner(System.in); 
System.out.println("Enter a string:"); 
str = sc.nextLine(); 
int length = str.length(); 
for ( int i = length - 1; i >= 0; i-- ) 
rev = rev + str.charAt(i); 
if (str.equals(rev)) 
System.out.println(str+" is a palindrome"); 
else 
System.out.println(str+" is not a palindrome"); 
} 
}

请问如何修改该程序，使其时间复杂度达到O(n)？

先给你理清楚为什么你现在的代码时间复杂度不是O(n)：

• Java里的String是不可变对象，每次执行rev = rev + str.charAt(i)的时候，都会创建一个全新的String对象，并且把之前rev里的所有字符都复制一遍再加新字符。这样每一次拼接的时间成本是当前rev的长度，整个循环下来总时间复杂度就变成了O(n²)。

下面给你两种高效的修改方案，都能把时间复杂度降到O(n)：

方案一：用StringBuilder构建反转字符串 #

StringBuilder是可变的字符序列，追加字符的操作是均摊O(1)时间，整体就能把时间复杂度控制在O(n)：

import java.util.Scanner;

class ChkPalindrome { 
    public static void main(String args[]) { 
        String str;
        StringBuilder rev = new StringBuilder(); 
        Scanner sc = new Scanner(System.in); 
        System.out.println("Enter a string:"); 
        str = sc.nextLine(); 
        int length = str.length(); 
        
        for (int i = length - 1; i >= 0; i--) {
            rev.append(str.charAt(i));
        } 
        
        if (str.equals(rev.toString())) {
            System.out.println(str + " is a palindrome"); 
        } else {
            System.out.println(str + " is not a palindrome"); 
        }
        
        sc.close(); // 别忘了关闭Scanner避免资源泄漏！
    } 
}

方案二：双指针法（更优，额外空间O(1)） #

不用构建完整的反转字符串，直接从字符串的首尾开始向中间对比字符，这样除了几个变量外不需要额外空间，时间复杂度依然是O(n)：

import java.util.Scanner;

class ChkPalindrome { 
    public static void main(String args[]) { 
        Scanner sc = new Scanner(System.in); 
        System.out.println("Enter a string:"); 
        String str = sc.nextLine(); 
        int left = 0;
        int right = str.length() - 1;
        boolean isPalindrome = true;
        
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                isPalindrome = false;
                break;
            }
            left++;
            right--;
        } 
        
        if (isPalindrome) {
            System.out.println(str + " is a palindrome"); 
        } else {
            System.out.println(str + " is not a palindrome"); 
        }
        
        sc.close();
    } 
}

补充说明： #

• 双指针法比第一种方案更省空间，因为它不需要复制整个字符串。
• 两种方案的时间复杂度都是O(n)：第一种是遍历一次字符串构建反转串，第二种是最多遍历一半字符串（遇到不同字符就提前终止），都属于线性时间。
• 记得关闭Scanner，避免不必要的资源占用。

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