探索 Java 中字符串里的回文：概念、实践与最佳方案

简介

在 Java 编程领域，处理字符串是一项常见任务，而判断字符串中的回文子串更是一个有趣且具有实际应用价值的问题。回文是指正读和反读都相同的序列，在字符串处理中，识别和处理回文子串可以应用于文本分析、数据验证等多个场景。本文将深入探讨在 Java 中处理字符串回文的相关内容，包括基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地掌握这一主题。

目录

1. 基础概念
   • 什么是回文
   • 字符串中的回文子串
2. 使用方法
   • 暴力解法
   • 中心扩展算法
   • Manacher 算法
3. 常见实践
   • 查找最长回文子串
   • 判断字符串是否包含回文子串
4. 最佳实践
   • 性能优化
   • 代码可读性与可维护性
5. 小结
6. 参考资料

基础概念

什么是回文

回文是一种特殊的序列，它从前往后读和从后往前读是完全一样的。例如，单词 "level"、"radar"，数字 "121" 等都是回文。在字符串的范畴中，回文可以是整个字符串，也可以是字符串中的一部分子串。

字符串中的回文子串

对于一个给定的字符串，其中可能包含多个回文子串。例如，在字符串 "banana" 中，"ana" 就是一个回文子串。找到字符串中的回文子串，尤其是最长回文子串，是一个经典的算法问题，在很多实际场景中都有应用，比如文本处理、密码验证等。

使用方法

暴力解法

暴力解法是最直接的方法，它通过遍历字符串的所有可能子串，并检查每个子串是否为回文。

public class PalindromeInString {
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static String longestPalindromeBruteForce(String s) {
        if (s == null || s.length() < 1) return "";
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String substring = s.substring(i, j + 1);
                if (isPalindrome(substring) && substring.length() > longest.length()) {
                    longest = substring;
                }
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        String input = "babad";
        System.out.println("Longest Palindrome (Brute Force): " + longestPalindromeBruteForce(input));
    }
}

中心扩展算法

中心扩展算法是一种更高效的方法。它基于回文的中心对称性，从字符串的每个字符和字符间隙开始向两边扩展，检查是否构成回文。

public class PalindromeInString {
    public static String longestPalindromeCenterExpansion(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        String input = "babad";
        System.out.println("Longest Palindrome (Center Expansion): " + longestPalindromeCenterExpansion(input));
    }
}

Manacher 算法

Manacher 算法是一种更为复杂但效率极高的算法，它可以在 O(n) 的时间复杂度内找到字符串中的最长回文子串。该算法通过在字符串中插入特殊字符，将奇数长度和偶数长度的回文统一处理。

public class PalindromeInString {
    public static String longestPalindromeManacher(String s) {
        if (s == null || s.length() == 0) return "";
        String t = preprocess(s);
        int[] p = new int[t.length()];
        int c = 0, r = 0;
        for (int i = 1; i < t.length() - 1; i++) {
            int i_mirror = 2 * c - i;
            if (r > i) {
                p[i] = Math.min(r - i, p[i_mirror]);
            } else {
                p[i] = 0;
            }
            while (t.charAt(i + 1 + p[i]) == t.charAt(i - 1 - p[i])) {
                p[i]++;
            }
            if (i + p[i] > r) {
                c = i;
                r = i + p[i];
            }
        }
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < t.length() - 1; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - 1 - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    private static String preprocess(String s) {
        if (s == null || s.length() == 0) return "^$";
        StringBuilder sb = new StringBuilder("^");
        for (char c : s.toCharArray()) {
            sb.append("#").append(c);
        }
        sb.append("#$");
        return sb.toString();
    }

    public static void main(String[] args) {
        String input = "babad";
        System.out.println("Longest Palindrome (Manacher): " + longestPalindromeManacher(input));
    }
}

常见实践

查找最长回文子串

上述代码中已经展示了不同方法查找最长回文子串。暴力解法简单易懂，但时间复杂度较高，适用于小数据量。中心扩展算法在效率上有所提升，是一种常用的方法。而 Manacher 算法则适用于对性能要求极高的场景。

判断字符串是否包含回文子串

public class PalindromeInString {
    public static boolean containsPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String substring = s.substring(i, j + 1);
                if (isPalindrome(substring)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String input = "abc";
        System.out.println("Contains Palindrome: " + containsPalindrome(input));
    }
}

最佳实践

性能优化

• 对于大规模数据，优先选择 Manacher 算法，它的时间复杂度为 O(n)，能显著提高效率。
• 在代码实现中，避免不必要的字符串创建和内存开销，如在中心扩展算法中，尽量复用已有的字符串对象。

代码可读性与可维护性

• 使用有意义的变量名和方法名，提高代码的可读性。例如，将扩展回文的逻辑封装到独立的方法中，如 expandAroundCenter。
• 添加注释，解释关键步骤和算法思路，方便后续维护和理解。

小结

在 Java 中处理字符串里的回文问题，有多种方法可供选择。从简单直接的暴力解法到高效的中心扩展算法和 Manacher 算法，每种方法都有其适用场景。在实际应用中，需要根据数据规模、性能要求和代码复杂度等因素综合考虑选择合适的方法。同时，通过遵循最佳实践原则，可以提高代码的质量和可维护性。

参考资料

• 《算法导论》
• LeetCode 相关题目及讨论区
• 各种 Java 编程论坛和技术博客