LeetCode Valid Palindrome双指针解法超时问题求助

问题背景 #

在解决LeetCode的Valid Palindrome问题时，双指针解法通过了479个测试用例，但在第480个长度为106890的超长字符串用例中超时；改用StringBuilder反转字符串后对比的方法却能通过所有测试用例。针对此情况，有以下疑问需要解答：

1. 为何双指针法会超时？
2. 理论上StringBuilder解法不该更慢吗？
3. 如何优化双指针解法？

附原始代码：

双指针解法代码 #

class Solution {
    public static boolean isPalindrome(String s) {
        String fixedString = "";
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c) || Character.isLetter(c)) {
                fixedString += c;
            }
        }
        fixedString = fixedString.toLowerCase();
        int i = 0;
        int j = fixedString.length() - 1;
        System.out.println(fixedString.toCharArray());
        while (i <= j) {
            if (fixedString.toCharArray()[i] != fixedString.toCharArray()[j]) {
                return false;
            }
            i += 1;
            j -= 1;
        }
        return true;
    }
}

StringBuilder解法代码 #

public class Valid_Palindrome {

    public static void main(String args[]){
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
    }

    public static boolean isPalindrome(String s) {
        String fixedString = "";
        for(char c : s.toCharArray()){
            if(Character.isDigit(c) || Character.isLetter(c)){
                fixedString += c;
            }
        }
        fixedString = fixedString.toLowerCase();
        StringBuilder sb = new StringBuilder(fixedString);
        sb = sb.reverse();
        System.out.println(sb);
        return sb.toString().equals(fixedString);
    }
}

疑问解答 #

1. 双指针法超时的原因 #

双指针思路本身没问题，超时是代码里的几个性能瓶颈导致的：

• String拼接低效：fixedString += c每次都会创建新的String对象（String是不可变类型），超长字符串场景下会生成大量临时对象，内存开销和GC成本极高。
• 循环重复生成char数组：fixedString.toCharArray()每次调用都会复制整个字符串生成新的char数组，while循环每轮调用两次，10万次循环下来，这个操作的时间开销呈指数级增长。
• 不必要的打印操作：System.out.println(fixedString.toCharArray())打印超长char数组会占用大量IO资源，严重拖慢执行速度。

2. 为何StringBuilder解法能通过？ #

虽然你的StringBuilder解法同样存在fixedString += c的低效问题，但核心逻辑（反转对比）是基于StringBuilder内部的char数组操作，reverse()方法是O(n)时间复杂度且直接操作数组，没有额外的重复复制开销。而双指针解法里的循环重复生成数组和打印操作的开销，远大于StringBuilder解法的反转开销，所以反而能通过测试。

3. 双指针解法的优化方案 #

针对上述问题，优化方向如下：

• 用StringBuilder做预处理拼接，避免频繁创建String临时对象；
• 提前转换为char数组，循环中直接访问数组元素，避免重复生成；
• 移除不必要的打印语句，提交代码时这类调试打印会严重影响性能；
• 进阶优化：直接在原字符串上双指针遍历，无需预处理整个字符串，左右指针直接跳过非字母数字字符，同时转换为小写对比，节省预处理的内存和时间。

优化后的双指针代码（两种版本）：

版本1：优化预处理的双指针解法

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder fixedSb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                fixedSb.append(Character.toLowerCase(c));
            }
        }
        char[] fixedChars = fixedSb.toString().toCharArray();
        int i = 0;
        int j = fixedChars.length - 1;
        while (i < j) {
            if (fixedChars[i] != fixedChars[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

版本2：无预处理的原地双指针解法（最优）

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            // 跳过左指针的非字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // 跳过右指针的非字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            // 转小写后对比
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

这个版本无需额外预处理整个字符串，空间复杂度为O(1)，时间复杂度为O(n)，是效率最高的解法。

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