当前位置：首页 > article >正文

leetcode hot100【LeetCode 5.最长回文子串】java实现

article 2024/11/17 18:08:25

LeetCode 5.最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。

示例 1:

输入: s = "babad"
输出: "bab"
解释: "aba" 也是一个有效答案。

示例 2:

输入: s = "cbbd"
输出: "bb"

说明:

1 <= s.length <= 1000
s 仅由数字和英文字母组成

Java 实现代码

public class Solution {
    public String longestPalindrome(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)) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

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

    // 中心扩展法
    private 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;  // 返回回文串的长度
    }
}

解题思路

该问题的核心是寻找字符串中最长的回文子串。回文子串的特点是从前向后和从后向前的字符相同。我们可以用几种方法来求解此问题，最常见的解法是通过
中心扩展法 来解决。

中心扩展法

回文的特点： 一个回文串可以通过其中心向两边扩展。例如，回文串 "aba" 的中心是 "b"，从中间扩展出去，得到回文串。

中心扩展法的核心思想：

每个字符（或每两个字符之间）可以看作回文的中心。
从该中心开始，尝试向左右两侧扩展，找到最大长度的回文子串。

具体步骤：

对于每个字符 i，考虑两种情况：
以字符 i 为中心的奇数长度回文串。
以字符 i 和 i+1 为中心的偶数长度回文串。

使用一个函数 expandAroundCenter(left, right) 来扩展回文串。
对每个字符中心调用扩展函数，记录最大长度的回文子串。