【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题解、大厂面试、大厂靠谱点对点内推 相关内容，公众号关注''一只编程熊"，获取信息吧！

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

巴特西

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

题意

题解

方法一

方法二

C++代码

Java代码

最新文章

热门文章