首页 > 其他 > 详细

LeetCode "Longest Palindromic Substring" - 1D DP

时间:2014-08-06 06:14:41      阅读:332      评论:0      收藏:0      [点我收藏+]

2D DP is an intuitive solution of course, but I got an MLE error, so I simplified it into a 1D DP:

class Solution {
public:
    void goDp(vector<int> &dp, int &maxLen, int &is, int &ie, int startLen, int len, string &s)
    {
        for(int ilen = startLen; ilen < len; ilen += 2)
        for(int i = 0; i < len - ilen; i ++)
        {
            bool bEq = s[i] == s[i + ilen];
            dp[i] = bEq ? (dp[i + 1] > 0 ? dp[i + 1] + 2 : 0) :    0;
            if( dp[i] > maxLen)
            {
                maxLen = dp[i];
                is = i; ie = i + ilen;
            }
        }
    }
    string longestPalindrome(string s) {
        int len = s.length();
        if(len == 0) return "";

        int maxLen = -1; int is = 0, ie = 0;
        //     Init
        vector<int> dp; dp.resize(len);
        
        //    Starting from 2
        for(int i = 0; i < len - 1; i ++)
        {
            if(s[i] == s[i + 1]) dp[i] = 2;
            else dp[i] = 0;
            if( dp[i] > maxLen)
            {
                maxLen = dp[i];
                is = i; ie = i + 1;
            }
        }        
        goDp(dp, maxLen, is, ie, 3, len, s);

        //    Starting from 1
        std::fill(dp.begin(), dp.end(), 1);
        goDp(dp, maxLen, is, ie, 2, len, s);

        return s.substr(is, ie - is + 1);
    }
};

Since loop on current length n depends linearly on dp data with length n-1, we can use 1D DP. And there are two cases of odd\even lengthes.

LeetCode "Longest Palindromic Substring" - 1D DP,布布扣,bubuko.com

LeetCode "Longest Palindromic Substring" - 1D DP

原文:http://www.cnblogs.com/tonix/p/3893606.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!