最长回文字符串题解(动态规划)

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

LeetCode正题

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

思考

回文字符串即正向顺序和反向顺序的字幕排序是一致的字段串。题的大意为寻找一个指定字符串中的最长的回文字符串。
首选,暴力解法需要遍历所有子串并判断子串是否为回文字符串。假设给定字符串长度n,那么子串的总数为​n(n+1)/2(即1 2 3 ... n的和),即需要O(n^2),然后判断每个子串是否为回文字符串的时间复杂度为O(n),即总共需要时间复杂度O(n^3)。时间肯定会超时的。
其中,上面暴力解法中的“判断子串是否为回文字符串”的时间复杂度可以优化到O(1)的。即利用动态规划思想,损耗O(n^2)的空间。
声明一个二维数组int dp[][],第一维表示子串的起始索引下标,第二维表示子串的结束索引下标,值为能区分是否为回文字符串的标志即可。判断当前子串是否为“回文字符串”的判断依据即,当前子串的首位字符相等,且舍去首位字符的子串也为“回文字符串”即可。这样,可以把判断子串是否为回文字符串的时间缩减到常量时间。即可以达到整体是时间复杂度为O(n^2)。
状态转移方程:
dp[s][e] = dp[s+1][e-1] && s[s] == s[e]

代码

/**
 * https://leetcode.com/problems/longest-palindromic-substring/solution/
 *
 * this demo:using the dp method, time O(n^2) space O(n^2)
 *
 */
#include <iostream>
#include <vector>
#include <map>
#include <string>

#define MAX 1001

using namespace std;

class Solution {
    private:
        string str;

    public:
        string longestPalindrome(string os) {
            str = os; // os:original string
            int dp[MAX][MAX] = {0};
            int ml = 0, ofs = 0, l = str.length(); // ml:max length ofs:offset
            for (int i = 0; i < l; ++i) {
                for (int j = i; j < l; ++j) {
                    if (isPalindrome(i, j, dp)) {
                        if (j - i + 1> ml) {
                            ofs = i;
                            ml = j - i + 1;
                        }
                    }
                }
            }
            return str.substr(ofs, ml);
        }

    private :
        bool isPalindrome(int s, int e, int dp[MAX][MAX]) { // s:start e:end
            if (dp[s][e] == 0) {
                switch (e - s + 1) {
                    case 1:
                        dp[s][e] = -1;
                        break;
                    case 2:
                        dp[s][e] = str[s] == str[e] ? -1 : -2;
                        break;
                    default:
                        dp[s][e] = (str[s] == str[e] && isPalindrome(s + 1, e - 1, dp))? -1 : -2;
                }
            }
            return dp[s][e] == -1 ? true : false;
        }
};

int main(int argc, char * argv[]) {
    Solution * s = new Solution();
    cout<<s->longestPalindrome("vommleztyrbrnoij");
}

结束语

当然,还可以将空间复杂度优化到O(1)(没有看懂,传送门 => Approach #4 (Expand Around Center) [Accepted]),时间复杂到优化到O(n)(利用Manacher算法,传送门 => Approach #5 (Manacher's Algorithm) [Accepted])。

 


参考文章:https://leetcode.com/problems/longest-palindromic-substring/solution/#approach-5-manachers-algorithm-accepted


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法 | 标签: , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。