首页 > 代码库 > 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.
思路：使用动态规划求解。
1 class Solution { 2 public: 3 string longestPalindrome( string s ) { 4 if( s.empty() ) { return string( "" ); } 5 int slen = s.length(), curlen = 1, ii = 0; 6 bool isPalindrome[2][1000]; 7 for( int step = 1; step < slen; ++step ) { 8 for( int i = 0; i <= slen-step; ++i ) { 9 int cur = (step-1) % 2;10 if( step <= 2 ) {11 isPalindrome[cur][i] = s[i] == s[i+step];12 } else {13 isPalindrome[cur][i] = s[i] == s[i+step] && isPalindrome[cur][i+1];14 }15 if( curlen < step+1 && isPalindrome[cur][i] ) {16 ii = i;17 curlen = step+1;18 }19 }20 }21 return s.substr( ii, curlen );22 }23 };
Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。