首页 > 代码库 > [LeetCode系列] 最长回文子串问题
[LeetCode系列] 最长回文子串问题
给定字符串S, 找到其子串中最长的回文字符串.
反转法: 反转S为S‘, 找到其中的最长公共子串s, 并确认子串s在S中的下标iS与在S‘中的下标iS‘是否满足式: length(S) = iS + iS‘ + length(s). 如果满足则s为搜索结果, 如果不满足我们就继续搜索.
DP解法:
定义 P[i][j] = true <-> Si...Sj是回文串, 否则为false;
则有 P[i+1][j-1] = true && Si = Sj <-> P[i][j] = true;
基本的情况则是 P[i][i] = true 以及 P[i][i+1] = (Si == Si+1)
从而我们可以在平方时间内构造和搜索完成, 并使用平方的空间.
1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 if (s.length() <= 1) return s; 5 // DP solution 6 bool P[1000][1000] = {false}; 7 int start = 0; 8 int maxLen = 0; 9 for (int i = 0; i < s.length(); i++) {10 P[i][i] = true;11 }12 for (int i = 0; i < s.length() - 1; i++) {13 if (s[i] == s[i+1]) {14 P[i][i+1] = true;15 start = i;16 maxLen = 2;17 }18 }19 for (int len = 3; len <= s.length(); len++) {20 for (int i = 0; i < s.length() - len + 1; i++) {21 int j = i + len - 1;22 if (s[j] == s[i] && P[i+1][j-1]) {23 P[i][j] = true;24 start = i;25 maxLen = len;26 }27 }28 }29 return s.substr(start, maxLen);30 }31 };中心法:
一个回文总是以某个字符为中心展开的, 这样的中心共有2N-1个(包括2个字符中间的"空白").
考虑到从中心开始拓展回文字符需要消耗O(N)次, 所以总的时间复杂度是O(N2).
1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 if (s.length() <= 1) return s; 5 string longest = s.substr(0, 1); 6 // Center Solution 7 for (int i = 0; i < s.length() - 1; i++) { 8 string res = expandFromCenter(s, i, i); 9 if (res.length() > longest.length()) longest = res;10 res = expandFromCenter(s, i, i+1);11 if (res.length() > longest.length()) longest = res;12 }13 return longest;14 }15 16 string expandFromCenter(string s, int l, int r) {17 while (l >= 0 && r < s.length() && s[l] == s[r]) {18 l--;19 r++;20 }21 return s.substr(l+1, r-l-1);22 }23 };
Manacher法: 线性时间解法, 比较复杂, 戳.
[LeetCode系列] 最长回文子串问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。