首页 > 代码库 > LeetCode "Longest Palindromic Substring" - 1D DP
LeetCode "Longest Palindromic Substring" - 1D DP
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.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。