首页 > 代码库 > Longest Palindromic Substring
Longest Palindromic Substring
最简单的可以采用暴力解法,时间复杂度O(n^3),但时间会溢出
方法:使用动态规划的方法
class Solution { public: string longestPalindrome(string s) { vector<vector<bool>> f(s.size(), vector<bool>(s.size(), false)); int maxLen = 1, start = 0; for(int i=0; i<s.size(); ++i) { f[i][i] = true; for(int j=0; j<i; ++j) { f[j][i] = (s[j] == s[i] && ((i-j<2)|| f[j+1][i-1])); if(f[j][i] && (i-j+1) > maxLen) { start = j; maxLen = i-j+1; } } } return s.substr(start, maxLen); } };
方法二:采用向两边扩展的方法
class Solution { public: string longestPalindrome(string s) { vector<char> tmp; tmp.push_back(‘_‘); for(int i=0; i<s.size(); ++i) { tmp.push_back(s[i]); tmp.push_back(‘_‘); } string ss = ""; for(int i=0; i<tmp.size(); ++i) ss += tmp[i]; int start = 0, maxLen = 1; for(int i=0; i<ss.size(); ++i) { int lt = i, rt = i; while(lt >= 0 && rt < ss.size() && ss[lt] == ss[rt]) { --lt; ++rt; } if((rt - lt - 2) > maxLen) { start = lt + 1; maxLen = rt - lt - 1; } } tmp.clear(); ss = ss.substr(start, maxLen); for(int i=0; i<ss.size(); ++i) if(ss[i] != ‘_‘) tmp.push_back(ss[i]); ss = ""; for(int i=0; i<tmp.size(); ++i) ss += tmp[i]; return ss; } };
Longest Palindromic Substring
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。