图解LeetCode——5. 最长回文子串（难度：中等）

爪哇缪斯

发布于 2023-05-10 11:13:13

1510

发布于 2023-05-10 11:13:13

文章被收录于专栏：爪哇缪斯爪哇缪斯

一、题目

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

二、示例

2.1> 示例 1：

【输入】s = "babad" 【输出】"bab" 【解释】"aba" 同样是符合题意的答案。

2.2> 示例 2：

【输入】s = "cbbd" 【输出】"bb"

提示：

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

三、解题思路

3.1> 通过中心点向两侧发散

因为本题是寻找最长回文字符串，所以，我们可以采取确定中心点之后，向两侧扩展的方式，来判断“扫描”到的子串是不是回文，如果是，则继续向两侧“扩展”，直到不满足回文条件为止。假设我们找到了一个回文字符串，其字符数存在两种情况，即：“奇数”字符个数和“偶数”字符个数。

对于奇数字符个数，中心点就是一个字符（即：head == tail），那么回文会以 2*N + 1的长度进行扩展。如下图所示：

对于偶数字符个数，中心点就是两个字符（即：head + 1 == tail），那么回文会以 2*N + 2的长度进行扩展。如下图所示：

整体遍历从头字符遍历到尾字符，在遍历过程中，当发现拼装的回文字符是现阶段最长的，则记录其mid和distinct（回文字符长度），当所有字符遍历完毕后，通过String的substring方法进行子字符串截图操作。

四、代码实现

4.1> 实现：通过中心点向两侧发散

class Solution {
    public String longestPalindrome(String s) {
        if (s == "" || s == null) {
            return null;
        }

        int mid = 0, distinct = 0;
        for (int i = 0; i < s.length(); i++) {
            int temp = Math.max(search(s, i, i), search(s, i, i + 1));
            mid = distinct < temp ? i : mid;
            distinct = Math.max(distinct, temp);
        }

        int num = (distinct % 2 == 0) ? 1 : 0; 
        return distinct == 0 ? null : s.substring(mid - distinct/2 + num, mid + distinct/2 + 1);
    }

    /**
     * 返回回文字符长度
     * 如果返回是【偶数】,则说明"中心点"是两个元素，即：head + 1 == tail
     * 如果返回是【奇数】,则说明"中心点"是一个元素，即：head == tail
     */
    public int search(String s, int head, int tail) {
        while (head >= 0 && tail < s.length() && s.charAt(head) == s.charAt(tail)) {
            head--;
            tail++;
        }
        return tail - head - 1;
    }
}