5. Longest Palindromic Substring

xiaoxiao2021-02-28  27

这个题的意思是,给出一个字符串s,返回他的最长回文子串(连续的)。

做过回文子串相关的动态规划的题目,所以很自然想到了动态规划。我的代码:

class Solution { public: string longestPalindrome(string s) { int res = 0; int n = s.size(); int idxx = 0, idxy = 0; vector<vector<int>> p(n, vector<int>(n, 1)); for(int i = 0; i < n; ++i) { p[i][i] = 1; } for(int i = 0; i < n; ++i){ for(int j = i-1; j >= 0; --j){ if(s[j] == s[i] && (i > j && p[j+1][i-1] == 1)){ p[j][i] = 1; if(i - j + 1 > res){ idxx = j; idxy = i; res = i-j+1; } }else{ p[j][i] = 0; } } } return s.substr(idxx, idxy - idxx + 1); } };看到大神写的更简短的代码,方法一样:

class Solution { public: string longestPalindrome(string s) { int dp[s.size()][s.size()] = {0}, left = 0, right = 0, len = 0; for (int i = 0; i < s.size(); ++i) { for (int j = 0; j < i; ++j) { dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1])); if (dp[j][i] && len < i - j + 1) { len = i - j + 1; left = j; right = i; } } dp[i][i] = 1; } return s.substr(left, right - left + 1); } };大神还提到一种马拉车算法:http://www.cnblogs.com/grandyang/p/4475985.html
转载请注明原文地址: https://www.6miu.com/read-1950015.html

最新回复(0)