Java字符串回文判断方法全解析

本文深入解析了Java中字符串回文判断的两种主流实现方式——高效节俭的双指针法（时间复杂度O(n)、空间复杂度O(1)）和简洁直观的StringBuilder反转法（空间复杂度O(n)），并强调预处理（统一大小写、过滤非字母数字字符）对实现语义正确回文判断的关键作用；同时延伸探讨了数字与链表等不同数据结构下的回文检测思路，揭示其背后共通的“对称性验证”本质与适配各自特性的巧妙设计，为开发者在性能、可读性与场景适配间提供清晰决策依据。

在Java中判断字符串是否为回文，核心方法有两种：双指针法和StringBuilder反转法。1. 双指针法通过设置左右指针，从字符串两端向中间逐个比较字符，若全部匹配则为回文，其时间复杂度为O(n)，空间复杂度为O(1)，性能更优，尤其适合处理长字符串；2. StringBuilder反转法则通过构建字符串的反转并与原字符串比较，虽然代码简洁但空间复杂度为O(n)，适用于字符串长度可控的场景。两种方法在判断前都需进行预处理，包括统一大小写和移除非字母数字字符，以确保回文判断符合语义要求，忽略大小写和标点符号的影响。

在Java里判断一个字符串是不是回文，核心思路无非就是看它正着读和反着读是不是一个样。这听起来简单，但实际操作起来，根据具体场景和性能要求，选择的方法会有些讲究。

解决方案

要实现回文判断，最直接且效率较高的方式是使用双指针法。

public class PalindromeChecker {

    public static boolean isPalindromeTwoPointers(String s) {
        if (s == null || s.isEmpty()) {
            return true; // 空字符串或null我们通常认为是回文
        }

        // 预处理：转小写，移除所有非字母数字字符
        // 这一步是为了让判断更通用，忽略大小写和标点符号
        String cleanedString = s.toLowerCase().replaceAll("[^a-z0-9]", "");

        int left = 0;
        int right = cleanedString.length() - 1;

        while (left < right) {
            if (cleanedString.charAt(left) != cleanedString.charAt(right)) {
                return false; // 发现不匹配，直接返回false
            }
            left++;
            right--;
        }
        return true; // 所有字符都匹配，是回文
    }

    // 另一种常见且简洁的方法是利用StringBuilder的反转功能
    public static boolean isPalindromeStringBuilder(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        String cleanedString = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        String reversedString = new StringBuilder(cleanedString).reverse().toString();
        return cleanedString.equals(reversedString);
    }

    public static void main(String[] args) {
        System.out.println("使用双指针法:");
        System.out.println("'madam' 是回文吗? " + isPalindromeTwoPointers("madam")); // true
        System.out.println("'A man, a plan, a canal: Panama' 是回文吗? " + isPalindromeTwoPointers("A man, a plan, a canal: Panama")); // true
        System.out.println("'hello' 是回文吗? " + isPalindromeTwoPointers("hello")); // false
        System.out.println("'Racecar' 是回文吗? " + isPalindromeTwoPointers("Racecar")); // true (处理后)

        System.out.println("\n使用StringBuilder反转法:");
        System.out.println("'madam' 是回文吗? " + isPalindromeStringBuilder("madam")); // true
        System.out.println("'A man, a plan, a canal: Panama' 是回文吗? " + isPalindromeStringBuilder("A man, a plan, a canal: Panama")); // true
    }
}

Java字符串回文检测：哪种方法性能更优？

在Java中，判断字符串回文的方法确实不止一种，上面我给出了两种常见的：双指针法和StringBuilder.reverse()法。要说哪个性能更优，这得具体分析它们背后的操作。

双指针法（isPalindromeTwoPointers）通常被认为是更优的选择，尤其是在处理非常长的字符串时。它的时间复杂度是O(n)，其中n是字符串的长度，因为它只需要遍历字符串大约一半的长度。更重要的是，它在空间复杂度上是O(1)（忽略预处理cleanedString的开销，如果直接在原字符串上处理，且允许修改，则更是如此），因为它不需要创建额外的数据结构来存储反转后的字符串。我们只是用两个指针在原字符串（或其清理后的版本）上移动比较。

而StringBuilder.reverse()法（isPalindromeStringBuilder），虽然代码看起来更简洁，但它在内部需要创建一个新的StringBuilder对象，然后对其进行反转操作，最后再转换回String进行比较。这个过程涉及到内存分配和字符串复制，所以它的空间复杂度是O(n)，时间复杂度也是O(n)。对于短字符串来说，这点开销可能微不足道，甚至因为JVM的优化，性能差异不明显。但当字符串非常长时，内存分配和复制的成本就会凸显出来，导致其性能劣于双指针法。

所以，如果追求极致性能和内存效率，特别是在处理大量或超长字符串的场景下，双指针法无疑是首选。但对于日常应用或字符串长度可控的情况下，StringBuilder.reverse()的简洁性也很有吸引力，可读性也相当不错。我个人在面试或竞赛中更倾向于双指针，因为它更能体现对算法复杂度的理解。

回文判断中的字符处理：如何应对空格、标点和大小写？

这是回文判断中一个非常实际且容易被忽略的问题。我们通常所说的“回文”，往往指的是忽略掉非字母数字字符（如空格、逗号、问号等）以及大小写之后，剩下的字符序列是回文。比如，“A man, a plan, a canal: Panama”就是一个经典的回文，但如果你不处理那些标点和空格，它显然不是。

要正确处理这些情况，关键在于“预处理”字符串。我的解决方案中已经包含了这一步：

1. 统一大小写： 使用s.toLowerCase()将整个字符串转换为小写（或大写）。这样，“Racecar”和“racecar”都能被正确识别为回文。
2. 移除非字母数字字符： 使用正则表达式replaceAll("[^a-z0-9]", "")来过滤掉所有不是小写字母（a-z）或数字（0-9）的字符。[^a-z0-9]这个正则表达式的含义是“匹配任何不是a到z或0到9的字符”。

预处理后的字符串，就只剩下我们需要比较的核心字符了，这时候再进行双指针或者反转比较，结果才是符合我们直觉的回文判断。忽略这一步，你的回文判断逻辑可能就会显得过于严格，无法识别那些“语义上”的回文。

当然，如果你有特殊需求，比如要求严格区分大小写，或者要求标点符号也参与回文判断（这在实际中很少见），那么你可以跳过或者调整预处理的步骤。但一般而言，上述的预处理是处理回文问题的标准做法，也是最符合用户预期的。

除了字符串，数字或链表如何进行回文检测？

回文的概念远不止局限于字符串。它本质上是一种对称性，这种对称性可以应用到各种数据结构上。

1. 数字回文判断： 判断一个整数是不是回文数，通常有两种思路：

• 转换为字符串： 这是最直观的方法，把整数转换成字符串，然后用我们上面讨论的字符串回文检测方法去判断。比如String.valueOf(number)。这种方法简单，但会涉及字符串转换的开销。
• 数学方法： 这种方法更“纯粹”，不涉及字符串转换。它的思路是逐步构建一个反转后的数字，然后与原数字进行比较。

  public static boolean isPalindromeNumber(int x) {
      if (x < 0 || (x % 10 == 0 && x != 0)) {
          return false; // 负数不是回文，以0结尾但本身不是0的数也不是回文 (如10, 100)
      }
      int reversedNum = 0;
      while (x > reversedNum) { // 当x小于或等于reversedNum时停止，避免溢出或重复比较
          reversedNum = reversedNum * 10 + x % 10;
          x /= 10;
      }
      // 对于偶数位数字，x会等于reversedNum
      // 对于奇数位数字，x会等于reversedNum / 10 (中间位不影响回文判断)
      return x == reversedNum || x == reversedNum / 10;
  }

  这种数学方法巧妙地避免了字符串转换，在性能上通常更优。

2. 链表回文判断： 判断一个单向链表是不是回文，这比字符串和数字复杂一些，因为单向链表只能从头向尾遍历，不能直接从尾部开始。常见的思路有：

• 转换为数组/列表： 遍历链表，将所有节点的值存储到一个ArrayList中，然后对ArrayList进行双指针回文判断。这种方法简单粗暴，但空间复杂度是O(n)。
• 快慢指针 + 反转后半部分： 这是更优雅且空间复杂度为O(1)的方法（如果允许修改链表结构）。
  1. 使用快慢指针找到链表的中间节点。
  2. 从中间节点开始，反转链表的后半部分。
  3. 现在，你有了链表的前半部分（从头开始）和反转后的后半部分。
  4. 同时遍历这两个部分，逐个比较节点的值。
  5. 比较完成后，为了不影响后续操作，通常需要将反转的后半部分再反转回来，恢复原链表结构。

链表的回文判断是一个经典的算法面试题，它考察的是对链表操作的熟练度和对空间复杂度的考量。可以看到，虽然数据结构不同，但核心的“对称性比较”思想是共通的，只是实现方式会根据数据结构的特性而变化。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《Java字符串回文判断方法全解析》文章吧，也可关注golang学习网公众号了解相关技术文章。