5. 最长回文子串

作者: Gunther17 | 来源:发表于2018-10-17 14:43 被阅读14次

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"

解法一：暴力解法
时间复杂度 $O(n^3)$
两个for循环，一个判断是否为回文的函数

解法二：中心扩展解法

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$
c++ code:

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<assert.h>
using namespace std;

class Solution {
public:
    string expand(string s,int left, int right)
    {
        int len = s.size();
        while (  left>=0&& right < len &&s[left] == s[right])//must s[left] == s[right] allocate last,unless crossing
        {
            left--;
            right++;

        }
        return s.substr(left + 1, right - left - 1);
    }
    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 1) return "";
        if (len == 1) return s;

        string maxstr=s.substr(0,1);
        for (int i = 0; i < len; i++)
        {
            string s1 = expand(s, i, i);
            if (s1.size()>maxstr.size())//odd number
            {
                maxstr = s1;
            }
            string s2 = expand(s, i, i + 1);//even number
            if (s2.size()>maxstr.size())
            {
                maxstr = s2;
            }
        }
        return maxstr;
    }
     
};

string stringToString(string input) {
    assert(input.length() >= 2);
    string result;
    for (int i = 1; i < input.length() - 1; i++) {
        char currentChar = input[i];
        if (input[i] == '\\') {
            char nextChar = input[i + 1];
            switch (nextChar) {
            case '\"': result.push_back('\"'); break;
            case '/': result.push_back('/'); break;
            case '\\': result.push_back('\\'); break;
            case 'b': result.push_back('\b'); break;
            case 'f': result.push_back('\f'); break;
            case 'r': result.push_back('\r'); break;
            case 'n': result.push_back('\n'); break;
            case 't': result.push_back('\t'); break;
            default: break;
            }
            i++;
        }
        else {
            result.push_back(currentChar);
        }
    }
    return result;
}

int main() {
    string line;
    while (getline(cin, line)) {
        string s = stringToString(line);

        string ret = Solution().longestPalindrome(s);

        string out = (ret);
        cout << out << endl;
    }
    return 0;
}

中心扩展test

substr
　　　Returns a substring (pos, pos+count).pos开始的位置，count共有多少个。

解法三：动态规划
时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$

核心思路就是从左开始遍历，然后不断的从原字符串中拿出1到length-1长度的字串，进行判断。回文字符串的子串也是回文，比如dp[j,k]（表示以i开始以j结束的子串）是回文字符串，那么dp[j+1,k-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。
　　动态规划需要开一个二维数组，DP[j][k]= s[j]==s[k]&&DP[j+1][k-1]，时间复杂度较高

初始化：
$\begin{cases} dp[j][j] = true & \text{(0 <= j <= n-1)}\\ dp[j][j+1] = true & \text{(0 <= j <= n-1,if s[j]==s[j+1])}\\ others = fasle \end{cases}$

转移函数
$dp[j][k] = \begin{cases} dp[j+1][k-1], & \text{if s[j] == s[k]} \\ false, & \text{if s[j] ≠ s[k]} \end{cases}$

class Solution {
public:

    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 1) return "";

        vector<vector<int>>Flaglen(len, vector<int>(len, 0));
        int maxlen = 0, index = 0;
        for (int i = 0; i < len; i++)
        for (int j = 0, k = i; j < len&&k < len; j++, k++)
        {
            if (j == k)Flaglen[j][k] = 1;//odd
            else if (j + 1 == k&&s[j] == s[k])
            {
                Flaglen[j][k] = 2;//even
            }
            else if (s[j] == s[k] && Flaglen[j + 1][k - 1])
            {
                Flaglen[j][k] = Flaglen[j + 1][k - 1] + 2;
            }
            else
            {
                Flaglen[j][k] = 0;
            }
            if (Flaglen[j][k]>maxlen)
            {
                index = j;
                maxlen = k - j + 1;
            }
        }
        return s.substr(index, maxlen);
    }


};

动态规划test

解法四：1975年，Manacher算法(马拉车)
时间复杂度 $O(n)$
1.解决长度奇偶性带来的对称轴位置问题
　　　插入#解决

string init(string s)
{
    string s1="$#";
    int len=s.size();
    int i;
    for(i=0;i<len;i++)
    {
        s1+=s[i];
        s1+="#";
    }

    return s1;
}

2.解决重复访问的问题
　　　利用最长id中心的当前i点的对称点j

好好思考体会这句代码：

if (i < mx)  
    p[i] = min(p[2 * id - i], mx - i);

step 1: 令p[i]=min(p[2*pos-i], mx-i)
step 2: 以i为中心扩展回文串，直到左右两边字符不同，或者到达边界。
step 3: 更新mx和id

示例：#a#和#a#a#回文半径分别是2和3，所以无论奇偶都是，p[i] - 1正好是原字符串中最长回文串的长度。
解释：原始字符串的最大子串，起始位置的索引centermax - maxlen) / 2，用下面的图验证。除以2是因为加入相同数的#。

举例验证

0	1	2	3	4	5	6	7	8
a	b	b	a	h	o	x	p	x

验证1：i=5,abba. centermax=5,maxlen=4,pos=0
验证2：i=16,pxp, centermax=16,maxlen=3,pos=6

class Solution {
public:
    string init(string s)
    {
        string s1 = "$#";//$防越界
        int len = s.size();
        for (int i = 0; i < len; i++)
        {
            s1 += s[i];
            s1 += '#';
        }
        return s1;
    }
    string longestPalindrome(string s) {
        int len1 = s.size();
        if (len1 < 1) return "";

        
        string s_new=init(s);
        int len = s_new.size();
        vector<int>p(len, 0);
        int id = 0, mx = 0;
        for (int i = 1; i < len; i++)//i从1开始忽略$
        {
            if (i < mx)
            {
                p[i] = min(p[2 * id-i], mx - i);
            }
            else//i在mx右边 必须一个个匹配
            {
                p[i] = 1;
            }
            while (s_new[i - p[i]] == s_new[p[i] + i])
                p[i]++;
            /*我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，
            这样才能更有机会执行 if (i < mx)这句代码，从而提高效率*/
            if (mx < i + p[i])
            {
                mx = i + p[i];
                id = i;
            }
        }
        /*找最大元素在P中*/
        int centermax = 0, maxlen = 0;
        for (int i = 1; i < len; i++)
        {
            if (p[i] - 1>maxlen)
            {
                maxlen = p[i] - 1;
                centermax = i;
            }
        }
        return s.substr((centermax - maxlen) / 2, maxlen);
    }


};

精益求精99.78%

参考1 此链接中心扩展ok，动态规划有问题。

参考2
参考3
参考4
Manacher

5. 最长回文子串

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

LeetCode试题详解