写点什么

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

发布于: 4 小时前
【LeetCode每日一题 Day 5】5. 最长回文子串


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

题意

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


示例


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

题解

方法一

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


// 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;    }};
复制代码


时间复杂度:


空间复杂度:

方法二

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


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


时间复杂度:


空间复杂度:


知识点总结: 枚举、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 题解、大厂面试、大厂靠谱点对点内推 相关内容,公众号关注''一只编程熊",获取信息吧!


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

发布于: 4 小时前阅读数: 6
用户头像

公众号: 一只编程熊 2021.06.30 加入

公众号: 一只编程熊;字节、旷视前员工,ACM金牌

评论

发布
暂无评论
【LeetCode每日一题 Day 5】5. 最长回文子串