aiaiask.com©

开花即结果 提问即答案

"Java ACM模式实现:寻找字符串中最长的回文子串"
原始问题:

"Java ACM模式实现:寻找字符串中最长的回文子串"

要找到一个字符串中最长的回文子串,可以使用中心扩展法来解决。具体步骤如下:

  1. 定义两个变量,start和end,用于记录最长回文子串的起始位置和结束位置。
  2. 遍历字符串s的每个字符,以当前字符为中心,向两边扩展,寻找回文子串。
  3. 分别处理回文子串长度为奇数和偶数的情况:

    • 对于奇数长度的回文子串,以当前字符为中心,向两边扩展,直到不满足回文条件为止。
    • 对于偶数长度的回文子串,以当前字符和下一个字符的中心,向两边扩展,直到不满足回文条件为止。
  4. 在扩展的过程中,记录最长回文子串的起始位置和结束位置。
  5. 最后,根据起始位置和结束位置,截取原字符串s中的最长回文子串。

以下是使用Java代码实现的示例:

public class Main {
    public static void main(String[] args) {
        String s = "babad";
        String longestPalindrome = findLongestPalindrome(s);
        System.out.println(longestPalindrome);
    }

    public static String findLongestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int start = 0;
        int 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) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

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

以上代码的输出结果为:"bab",即为字符串 "babad" 中的最长回文子串。

"Java ACM模式实现:寻找字符串中最长的回文子串"
https://www.aiaiask.com/ask/45594.html
AI / 模型Siliconflow
时间 / DATEAugust 30, 2023, 8:06 PM
语言zh-CN
IP / 区域陕西 西安