首页 > 代码库 > Longest Palindromic Subsequence
Longest Palindromic Subsequence
方法:与substring的不同是这里不需要子串连续
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>> f(s.size(), vector<int>(s.size(), 0)); for(int i=s.size()-1; i>=0; --i) { f[i][i] = 1; for(int j=i+1; j<s.size(); ++j) { if(s[i] == s[j]) f[i][j] = f[i+1][j-1] + 2; else f[i][j] = max(f[i+1][j], f[i][j-1]); } } return f[0][s.size()-1]; } };
或者
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>> f(s.size(), vector<int>(s.size(), 0)); for(int i=0; i<s.size(); ++i) { f[i][i] = 1; for(int j=i-1; j>=0; --j) { if(s[i] == s[j]) f[j][i] = f[j+1][i-1] + 2; else f[j][i] = max(f[j+1][i], f[j][i-1]); } } return f[0][s.size()-1]; } };
Longest Palindromic Subsequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。