【LeetCode每日一题 Day 5】5. 最长回文子串

一只编程熊
• 阅读 1819

【LeetCode每日一题 Day 5】5. 最长回文子串

大家好,我是编程熊,今天是LeetCode每日一题的第五天,一起学习LeetCode第五题《最长回文子串》。

题意

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

示例

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

题解

方法一

采用简单暴力的方法,枚举每一个位置为单独回文中心(长度为奇数的子串,如 aba)或者回文中心中的一个(长度为偶数的子串,如abba),同时向左和向右扩展查看是否相等,直至 不相等 或 到字符串开头/结尾 停止扩展。最坏的情况下,如 aaaaaa ,时间复杂度为 $O(n^2)$。

// C++代码
class Solution {
public:
    string longestPalindrome(string s) {
        int st = 0, ed = 0;
        for (int i = 0; i < s.size(); i++) {
            auto ans1  = expandMaxLen(s, i, i);
            auto ans2  = expandMaxLen(s, i, i + 1);
            if (ans1.second - ans1.first > ed - st) {
                ed = ans1.second;
                st = ans1.first;
            }
            if (ans2.second - ans2.first > ed - st) {
                ed = ans2.second;
                st = ans2.first;
            }
        }
        return s.substr(st, ed - st +  1);
    }
    pair<int, int>  expandMaxLen(string s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            --l;
            ++r;
        }
        pair<int, int> ans = {l + 1, r - 1};
        return ans;
    }
};

时间复杂度: $O(n^2)$

空间复杂度: $O(n)$

方法二

Manacher算法 可以在 $O(n)$ 的时间复杂度下,求字符串的最长回文子串,后续会专门出一篇文章讲解 Manacher算法

下面代码给的是 Manacher算法 解决的,代码超过了99.9%的解法,大家可以先理解一下。

时间复杂度: $O(n)$

空间复杂度: $O(n)$

知识点总结: 枚举、Manacher算法。

C++代码

class Solution {
public:
    string longestPalindrome(string s) {
        string str = preSovle(s);
        int max_id = 0, max_pos = 0, ans_pos, ans_len = 0;
        vector<int> arm_len(str.size(), 0);
        for (int i = 2; i <= str.size() - 2; i++) {
            if (max_pos > i) arm_len[i] = min(max_pos - i, arm_len[2 * max_id - i]);
            else arm_len[i] = 1;
            while (str[i + arm_len[i]] == str[i - arm_len[i]]) arm_len[i]++;
            if (i + arm_len[i] > max_pos) {
                max_pos = i + arm_len[i];
                max_id = i;
            }
            if (arm_len[i] - 1 > ans_len) {
                ans_len = arm_len[i] - 1;
                ans_pos = i;
            }
        }
        int pos = (ans_pos - 2) / 2;
        return str[ans_pos] == '#' ? s.substr(pos - ans_len / 2 + 1, ans_len):
                                     s.substr(pos - ans_len / 2, ans_len);
    }
    string preSovle(string s) {
        string str = "$";
        for (int i = 0; i < s.size(); i++) {
            str += '#';
            str += s[i];
        }
        str += '#', str += '*';
        return str;
    }
};

Java代码

class Solution {
    public String longestPalindrome(String s) {
        String str = preSolve(s);
        int max_id = 0, max_pos = 0, ans_pos = 0, ans_len = 0;
        int[] arm_len = new int[str.length()];

        for (int i = 2; i <= str.length() - 2; i++) {
            if (max_pos > i) arm_len[i] = Math.min(max_pos - i, arm_len[2 * max_id - i]);
            else arm_len[i] = 1;
            while (str.charAt(i + arm_len[i]) == str.charAt(i - arm_len[i])) arm_len[i]++;
            if (i + arm_len[i] > max_pos) {
                max_pos = i + arm_len[i];
                max_id = i;
            }
            if (arm_len[i] - 1 > ans_len) {
                ans_len = arm_len[i] - 1;
                ans_pos = i;
            }
        }
        int pos = (ans_pos - 2) / 2;
        return str.charAt(ans_pos) == '#' ? s.substring(pos - ans_len / 2 + 1, pos - ans_len / 2 + ans_len + 1):
            s.substring(pos - ans_len / 2, pos - ans_len / 2 + ans_len);
    }

    public String preSolve(String s) {
        String str = "$";
        for (int i = 0; i < s.length(); i++) {
            str = str.concat("#");
            str += s.charAt(i);
        }
        str += '#';
        str += '*';
        return str;
    }
}

题目链接: https://leetcode-cn.com/problems/longest-palindromic-substring/

我是编程熊,持续输出 LeetCode题解、大厂面试、大厂靠谱点对点内推 相关内容,公众号关注''一只编程熊",获取信息吧!

欢迎 『关注』、『点赞』、『转发』支持~

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
Kubrnete Kubrnete
3年前
动态规划之马拉车算法
问题描述:给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。如"abc"有三个回文子串‘a','b','c'.示例1:输入:"abc"输出:3解释:三个回文子串:"a","b","c"示例2:输入:"aaa"输出
Stella981 Stella981
2年前
JS 苹果手机日期显示NaN问题
问题描述newDate("2019122910:30:00")在IOS下显示为NaN原因分析带的日期IOS下存在兼容问题解决方法字符串替换letdateStr"2019122910:30:00";datedateStr.repl
Stella981 Stella981
2年前
HDU 2594(求最长公共前后缀 kmp)
题意是在所给的两个字符串中找最长的公共前后缀,即第一个字符串前缀和第二个字符串后缀的最长相等串。思路是将两个字符串拼接在一起,然后直接套用kmp算法即可。要注意用next会报编译错误,改成Next才过……但next确实不是c关键字。代码如下:!(https://oscimg.oschina.net/oscnet/5
Wesley13 Wesley13
2年前
125. 验证回文串
\TOC\题目给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。说明:本题中,我们将空字符串定义为有效的回文串。示例1:输入:"Aman,aplan,acanal:Panama"输出:true示例2:输入:"raceacar"输出
Stella981 Stella981
2年前
LeetCode 226场周赛题解
❝【GiantPandaCV导语】这是LeetCode第226场周赛题解,本周考察的知识点有枚举,贪心,前缀和,Manacher回文算法,动态规划,图论等。❞比赛链接https://leetcodecn.com/contest/weeklycontest226/最终Rank:23
Stella981 Stella981
2年前
Lua 字符串查找函数 string.find(s, pattern [, init [, plain]] )【转】
函数原型string.find(s,pattern\,init\,plain\\)s:源字符串pattern:待搜索模式串init:可选,起始位置plain:我没用过①子串匹配:print(string.find("haha",'ah'))输出23注意:
Stella981 Stella981
2年前
LeetCode:(14. 最长公共前缀!!!!!)
题目:14\.最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串“”。示例1:输入:\“flower”,“flow”,“flight”\输出:“fl”示例2:输入:\“dog”,“racecar”,“car”\输出:“”
Stella981 Stella981
2年前
LeetCode459. 重复的子字符串
1.问题描述给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。示例1:输入:“abab”输出:True解释:可由子字符串“ab”重复两次构成。示例2:输入:“aba”输出:Fal
Stella981 Stella981
2年前
Leetcode 424.替换后的最长重复字符
替换后的最长重复字符给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 _k_次。在执行上述操作后,找到包含重复字母的最长子串的长度。注意:字符串长度和_k_不会超过 104。示例1:输入:s"ABAB",k2输
一只编程熊
一只编程熊
Lv1
公众号: 一只编程熊;字节跳动、旷视科技员工,ACM金牌
文章
2
粉丝
1
获赞
2