当前位置: 首页 > >

LeetCode OJ 之 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,找出S中最长的回文子串。你可以假定S的最大长度为1000.并且存在一个唯一的最长回文子串。


思路:


1、暴力枚举


2、动态规划,复杂度 O( n ^2)。设状态 f(i,j) ,表示区间 [i,j] 是否为回文串,则状态转移方
程为
f( i, j) = ? true ; i == j;
? ? ??s[i] == s[j] ;j = i + 1;
? ? ??s[i] == s[j] && f(i+1 , j-1); ? ?j > i + 1;


其中i < j


动态规划代码:



class Solution {
public:
//动态规划法
//f( i, j) = true ; i == j;
// s[i] == s[j] ;j = i + 1;
// s[i] == s[j] && f(i+1 , j-1); j > i + 1
string longestPalindrome(string s)
{
bool f[1000][1000]={false};
string result;
int start = 0;//记录最长回文子串的起始点
int maxLen = 1;//记录最长回文子串的长度
if(s.empty() || s.size() == 1)
return s;
int len = s.size();f[0][0] = true;
//只计算矩阵f的上三角,每一次for循环计算上三角的一列
for(int j = 1 ; j < len ; j++)
{
f[j][j] = true;//对角线为true,只有一个元素,是回文
for(int i = 0 ; i < j ; i++)
{
if( j == i + 1 && s[i] == s[j])//计算靠*对角线的那个
f[i][j] = true;
if(j > i + 1 )//由前一列和s[i]s[j]求当前列的元素,前一列的元素值已经由上个for循环计算出来
{
f[i][j] = ( s[i] == s[j] && f[i + 1][j - 1]);
}
if(f[i][j] && j-i+1 > maxLen)
{
start = i;
maxLen = j-i+1;
}

}
}
return s.substr(start,maxLen);//返回以start开头,长度为maxLen长度的子串
}

};

3、从i向两边扩展



class Solution {
public:
string longestPalindrome(string s)
{
size_t len = s.size();
int start = 0 , maxLen = 1;
for(int i = 0 ; i < len-1 ; i++)
{
if(len - i <= maxLen/2)
break;
int j = i , k = i+1;
while(j >= 0 && k < len && s[j] == s[k])
{
j--;
k++;
}
if(k-j-1 > maxLen)
{
maxLen = k-j-1;
start = j+1;
}
j = i , k = i;
while(j >= 0 && k < len && s[j] == s[k])
{
j--;
k++;
}
if(k-j-1 > maxLen)
{
maxLen = k-j-1;
start = j+1;
}
}
return s.substr(start , maxLen);
}
};








友情链接: