本文主要是介绍918-最长回文子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

方法一：暴力求解

时间复杂度：O(N^3)
空间复杂度：O(1)
思路：思路很简单，双循环判断每一个从i开始到j结束的子串是不是回文的，因为判断子串又需要遍历一遍
所以时间复杂度为O(N^3)

class Solution 
{//暴力算法
public:
    string longestPalindrome(string s)
    {
        if (s.size() == 0 || s.size() < 2) return s;
        int max = 0;
        string ret = "";
        for (int i = 0; i < s.size(); i++)
        {
            for (int j = 1; j < s.size(); j++)
            {
                string tmp = s.substr(i, j - i + 1);
                string tmpr(tmp);//这里将这个子串反转一下与原串对比是否相同
                reverse(tmp.begin(), tmp.end());
                if (tmp == tmpr && tmp.size() > max)
                {
                    max = tmp.size();
                    ret = s.substr(i, j - i + 1);
                }
            }
        }
        return ret;
    }
};

方法二-中心扩散算法

这个算法相对暴力算法来说可以说效率高了不只一点点，甚至比动态规划还要好。

时间复杂度：O(N^2)
空间复杂度：O(1)
思路：
以abbba为例子，我们以最中间的b为例子，向两边扩散为bbb -> abbba,结束。
当然如果是abba的字符串我们就可能需要从bb开始扩散bb -> abba结束，思路并不难理解照着源代码就能豁然开朗。

class Solution 
{//中心扩散法
public:
    int max = 0;
    string ret = "";
    void spread(string& s, int left, int right) 
    {
        int L = left, R = right;
        while (L >= 0 && R < s.size() && s[L] == s[R])
        {//向左向右扩散
            if (R - L + 1 > max) 
            {
                max = R - L + 1;
                ret = s.substr(L, R - L + 1);
            }
            L--; R++;
        }
    }
    string longestPalindrome(string s) 
    {
        if (s.size() <= 1) return s;
        for (int i = 0; i < s.size(); i++) 
        {
            spread(s, i, i);//从单个字符开始扩散
            spread(s, i, i + 1);//从相邻的两个字符开始扩散
        }
        return ret;
    }
};

方法三：动态规划

时间复杂度：O(N^2)
空间复杂度：O(N^2)

思路：一个子串是否为回文串可以判断这个子串的第一个与最后一个是否相等+中间的子串是否为回文，中间的子串又可以分解为第一个与最后一个是否相等+中间的子串是否为回文，所以我们就找到了最优子结构，我们直接贴代码来分析

class Solution 
{//动态规划
public:
    string longestPalindrome(string s)
    {
        if (s.size() == 0)
        {
            return s;
        }
        const int n = s.size();
        int dp[n][n] = { 0 };//创建一个存放状态的数组
        string ret = "";
        int max = 0;
        for (int i = 0; i < s.size(); i++)
        {//这个双循环是在判断i到j位置的子串是否为回文串
            for (int j = 0; j <= i; j++) 
            {
                dp[i][j] = s[i] == s[j] && (i - j <= 2 || dp[i - 1][j + 1]);
                //i-j <=2这句是因为如果子串为bb时就是极限状态，他也构成回文
                //dp[i-1][j+1]这句就是判断中间的子串是否为回文，很好理解
                if (dp[i][j]) 
                {
                    if (i - j + 1 > max) 
                    {
                        max = i - j + 1;
                        ret = s.substr(j, i - j + 1);
                    }
                }
            }
        }
        return ret;
    }
};

方法四：马拉车算法

链接：马拉车算法解析

class Solution 
{//马拉车算法
public:
    string longestPalindrome(string s)
    {
        if (s.size() <= 1) return s;
        string str = "@#";//一定注意这个@，非常关键，因为在从下标为1的#字符开始求解p数组时没有这个符号就越界了
        for (int i = 0; i < s.size(); i++) 
        {
            str += s[i];
            str += '#';
        }

        vector<int> p(str.size(), 0);
        int mx = 0, id = 0, start = 0, maxlen = 0;
        for (int i = 1; str[i] != '\0'; i++) 
        {
            //这里如果i在右边界mx之外就只能自己老实匹配了，如果在mx之内需要看p[j]是否大于对称的mx左边界，大于的话说明i位置
            //的p[i]至少也能延展到以id为中心的回文边界，否则只能是p[j]的值
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (str[i + p[i]] == str[i - p[i]]) p[i]++;
            if (i + p[i] > mx) 
            {
                mx = i + p[i];
                id = i;
            }
            if (p[i] - 1 > maxlen)
            {
                start = (i - p[i]) / 2;//i+p[i]是右边界，所以i-p[i]就是左边界，除以2是因为str加了#变成了两倍长度，所以
                //在原串的开始位置就是除以2
                maxlen = p[i] - 1;
            }
        }
        return s.substr(start, maxlen);
    }
};

这篇关于918-最长回文子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！