首页 > 代码库 > leetcode 5.Longest Palindromic Substring
leetcode 5.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.
求最长回文子串，假设我们已知S[i...j]是回文子串，那么，若S[i-1] = S[j+1]，则S[i-1,...,j+1]是回文子串。
用table[i][j]的true/false表示S[i,...,j]是否为回文子串，
可以得到递推公式：table[i][j] = table[i+1][j-1] && (S[i] == S[j]) (i+1 <= j-1, 即 i+2 <= j)
初始条件：
当j = i 时，table[i][j] = true;
当j = i + 1时，table[i][j] = (S[i] == S[j])
1 string longestPalindrome(string s) 2 { 3 bool table[1000][1000] = {false}; 4 int i, j, slen = s.length(), start = 0, maxlen = 1; 5 6 for (i = 0; i < slen; i++) 7 table[i][i] = true; 8 for (i = 0; i < slen - 1; i++) 9 {10 j = i + 1;11 if (s[i] == s[j])12 {13 table[i][j] = true;14 start = i;15 maxlen = 2;16 }17 }18 19 for (int len = 3; len <= slen; len++)20 {21 for (i = 0; i < slen - len + 1; i++)22 {23 j = i + len - 1;24 if (s[i] == s[j] && table[i + 1][j - 1])25 {26 table[i][j] = true;27 start = i;28 maxlen = len;29 }30 }31 }32 33 return s.substr(start, maxlen);34 }
leetcode 5.Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。