如何在排除非字母数字字符的情况下检查回文字符串？

需求说明 #

实现一个功能：在排除所有非字母数字字符的前提下，检查给定字符串是否为回文。

初始实现代码 #

public String isPalindrome(String s) {

    String trimmed = s.replaceAll("[^A-Za-z0-9]", "");

    String reversed = "";

    int len = trimmed.length();

    for (int i = len - 1; i >= 0; i--) {
        char[] allChars = trimmed.toCharArray();
        reversed += allChars[i];
    }

    if (trimmed.equalsIgnoreCase(reversed)) {
        return "true";
    } else {
        return "false";
    }
}

测试示例 #

示例1 #

• 输入：A man, a plan, a canal: Panama
• 输出：true
• 解释：仅保留字母数字字符后得到AmanaplanacanalPanama，忽略大小写后是回文。

示例2 #

• 输入：race a car
• 输出：false
• 解释：仅保留字母数字字符后得到raceacar，忽略大小写后并非回文。

代码优化方案 #

你的初始代码可以正常工作，但存在几个可以提升效率和规范性的点：

1. 避免重复生成字符数组：循环内每次调用trimmed.toCharArray()会重复创建相同的字符数组，完全可以把这一步移到循环外面。
2. 替换字符串拼接方式：用+=拼接字符串会频繁创建新的String对象，改用StringBuilder能大幅提升循环中的拼接效率。
3. 返回布尔类型而非字符串：Java中判断类方法的返回值用boolean类型更符合语义，也便于后续逻辑处理。

优化后的版本：

public boolean isPalindrome(String s) {
    // 过滤非字母数字并统一转为小写，减少后续比较的开销
    String filtered = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
    int length = filtered.length();
    StringBuilder reversed = new StringBuilder(length);

    for (int i = length - 1; i >= 0; i--) {
        reversed.append(filtered.charAt(i));
    }

    return filtered.equals(reversed.toString());
}

更高效的双指针实现 #

如果追求更高的空间效率，可以使用双指针法，不需要额外创建反转后的字符串，空间复杂度降至O(1)：

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;
}

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