首页 > 代码库 > Leetcode:Longest Palindromic Substring 最长回文子串
Leetcode:Longest Palindromic Substring 最长回文子串
Longest Palindromic Substring：
Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
解题分析：
设f[i][j]表示[i,j]之间的最长回文子串，递推方程如下：
class Solution {public: string longestPalindrome(string s) { if (s.size() == 0) return ""; const int strLen = s.size(); bool flag[strLen][strLen]; memset(flag, false, sizeof(flag)); //vector<vector<bool>> flag(strLen, vector<bool>(strLen, false)); int maxLen = 1; int start = 0; for (int i = strLen - 1; i >= 0; --i) { flag[i][i] = true; for (int j = i + 1; j < strLen; ++j) { if (j == i + 1 && s.at(i) == s.at(j)) flag[i][j] = true; if (j > i + 1 && s.at(i) == s.at(j) && flag[i+1][j-1] == true) flag[i][j] = true; if (flag[i][j] == true && maxLen < j - i + 1) { maxLen = j - i + 1; start = i; } } } return s.substr(start, maxLen); }};
注意：
因为f[i,j] 需要使用到 f[i+1, j-1]，所以必须首先计算 f[i+1, j-1], 然后计算 f[i,j] 这样游标i必须从大到小，游标j必须从小到大
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。