【每日leetcode】18.最长回文子串

一条coding

发布于 2021-08-12 10:36:41

3000

发布于 2021-08-12 10:36:41

文章被收录于专栏：一条IT

⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐

回文的意思是正着念和倒着念一样，如：上海自来水来自海上 ——leetcode此题热评在对联中就有回文的手法，“上海自来水来自海上”，大家有下联了吗

前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

今天来一道中等题，看看自己功力几何？

Question

5. 最长回文子串

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：

1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成

Solution

之前我们做过一道题是：「最长不重复子串」。当时使用的是滑动窗口法。这道题增加了回文的约束，那么该怎么处理回文，可以在纸上写一个回文串观察一下，有什么特点呢？从中心点向两端发散对吧，所以我们要滑动这个中心点，并对每一个中心点，进行左右扩展，判断左右字符是否相等即可。

把null和空字符串的特殊情况处理掉
有一个可滑动且大小可变的窗口，窗口左端（start）不动，右端（end）向后移动
由于字符串长度有奇数和偶数两种，所以我们需要同时计算从一个字符开始扩展和从两个字符之间开始扩展
找出两种扩展中相对长的作为当前最大值
新的start要从何处开始，如何扩展字符串只需要考虑的问题

还有一种「马拉车算法」更加快速，但有一定难度，面试一般不会出现，感兴趣的同学可以看一下

Code

所有leetcode代码已同步至github https://github.com/lbsys 欢迎star

/**
 * @author yitiaoIT
 */
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) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}