Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Longest Palindromic Substring

Leetcode algorithms 第 5 题:Longest Palindromic Substring。

题目

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

解答1

要判断一个子串是否为回文串,只需要判断首尾是否相等:

  • 如果不相等,不可能回文。
  • 如果相等,则只需要判断中间长度较短的子串是否为回文串。

这样显然可以看到动态规划的思路,令dp[i][j]表示从i到j的子串是否为回文串,则dp[i][j] = s[i]==s[j] &&dp[i+1][j-1]。

具体代码如下:

string longestPalindrome(string s) { //动态规划算法
        
        int n = s.size(), mxlen = 1, st = 0; //长度,最长回文长度及起点
        
        bool dp[1001][1001] = {0}; 
        for (int i = 0; i < n; i++)  //长度为1,全是回文
            dp[i][i] = 1;
        for (int i = 0; i < n-1; i++)//长度为2,相等才是回文
            if (s[i] == s[i+1])
                dp[i][i+1] = 1, mxlen = 2, st = i;

        for (int len = 3; len <= n; len++) //长度
            for (int i = 0, j = i + len - 1; j < n; i++, j++) //i、j为起点、终点
                if (s[i] == s[j] && dp[i+1][j-1])//首尾相同,并且中间是回文
                    dp[i][j] = 1, mxlen = len, st = i;
        
        return s.substr(st, mxlen);
    }

解答2

上述算法时间复杂度为O(n^2),而且需要O(n^2)空间,较为复杂,这里使用另一个较为高效的算法:Manacher算法。

回文串的情况分成两种:

  • 奇数长度,如aba,最中间元素只出现一次
  • 偶数长度,如abba,最中间元素出现两次

Manacher算法在源字符串的首尾和中间分别嵌入分隔符,把以上两种情况统一为一种情况(奇数长度的情况),即

  • 原本奇数长度,如aba,变成#a#b#c#,即以b为中心的回文子串
  • 原本偶数长度,如abba,变成#a#b#b#a,,即以最中间的#为中心的回文子串

这样可以方便后续统一处理,同时也容易从新的回文子串中求得原有的回文子串。为了方便,还在字符串的首尾添加另外没有出现过的字符作为分隔符,如^和$。

算法使用数组p[i]记录了以每个字符为中心时最长回文串的长度,但是它在计算p[i]时,利用了以前的信息,使得不需要重新匹配部分内容,最终达到O(n)时间复杂度的效果。

在遍历i计算p[i]时,使用id表示以id为中心时最长回文串的边界走得最远,这个最远的位置为maxid。则如果i位于maxid以内,则可以利用i关于id的镜像位置2*id-i的信息,因为该位置的p[2*id-1]已经计算过了,而根据镜像关系,可以知道,其对应的回文在位置i仍然形成回文,于是p[i]至少应该为p[2*id-1]。但是p[i]加上p[2*id-1]后不能超过当前的maxid,因为后面的元素还没有记录。
得到p[i]的初值后,可以继续往后遍历看能否p[i]能否继续加大,最终更新新的id和maxid的值。

由于maxid在遍历过程中是递增的,整个算法的复杂度只是O(n)。

得到p[i]数组后,可以找到最大的一个及其对应的中心位置,然后在原数组找到对应的子串,具体参考代码如下:

string longestPalindrome(string s) { //Manacher算法
        string str = "^#"; //添加分隔符
        for (int i = 0; i < s.size(); i++) str += s.substr(i, 1) + "#";
        str += "$";
        
        int n = str.size();
        int p[2100] = {0}; //p[i]表示以i为中心的最长回文子串的长度,只是一边的长度
        int mxid = 0, id;  //id表示当前能够走的最远的起点,mxid即为最远的位置
        
        for (int i = 1; i < n-1; i++)
        {
            if (mxid > i) //i在最远距离以内,可以根据镜像位置得到p[i]
                p[i] = min(p[2*id-i], mxid-i);
            else 
                p[i] = 1;
            
            while (str[i+p[i]] == str[i-p[i]]) p[i]++;   //继续匹配
            if (i + p[i] > mxid) mxid = i + p[i], id = i;//更新最远位置
        }
        
        int mxlen = 0, mid; //寻找最长回文串的中点和长度
        for (int i = 1; i < n-1; i++)
            if (p[i] > mxlen) mxlen = p[i]-1, mid = i;
        return s.substr((mid-1-mxlen)/2, mxlen);
    }
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论