【算法练习02】5最长回文子串——滑动窗口

发表于

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动

本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

⭐本文收录于github-JavaExpert，技术专家修炼之路，包含Java完整学习路线及配套学习资料，欢迎star⭐

回文的意思是正着念和倒着念一样，如：上海自来水来自海上

——leetcode此题热评

在对联中就有回文的手法，“上海自来水来自海上”，大家有下联了吗

iShot2021-10-13 11.38.07.png

前言

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

糊涂算法，难得糊涂

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

Question

5. 最长回文子串

难度：中等

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

示例 1：

1
2
3
4
5
> arduino复制代码输入：s = "babad"
> 输出："bab"
> 解释："aba" 同样是符合题意的答案。
> 
>

示例 2：

1
2
3
4
> ini复制代码输入：s = "cbbd"
> 输出："bb"
> 
>

示例 3：

1
2
3
4
> ini复制代码输入：s = "a"
> 输出："a"
> 
>

示例 4：

1
2
3
4
> ini复制代码输入：s = "ac"
> 输出："a"
> 
>

提示：

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

Solution

之前我们做过一道题是：最长不重复子串。当时使用的是滑动窗口法。

这道题增加了回文的约束，那么该怎么处理回文，可以在纸上写一个回文串观察一下，有什么特点呢？

从中心点向两端发散

对吧，所以我们要滑动这个中心点，并对每一个中心点，进行左右扩展，判断左右字符是否相等即可。

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

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

Code

所有leetcode代码已同步至github

欢迎star

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
java复制代码/**
 * @author 一条coding
 */
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;
}

Result

复杂度分析

  • 时间复杂度：O(N)

image-20210802132533270

Last

独脚难行,孤掌难鸣，一个人的力量终究是有限的，一个人的旅途也注定是孤独的。当你定好计划，怀着满腔热血准备出发的时候，一定要找个伙伴，和唐僧西天取经一样，师徒四人团结一心才能通过九九八十一难。所以，请加入组队刷题。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%