經典算法題--求對策字符串的最大長度(第二版)
經典算法題--求對策字符串的最大長度(第二版)
方法一：思路很中規中矩，遍歷這個字符串，若有發現相鄰的兩個字符相等，就循環判斷與這兩個字符相鄰的兩個字符是否相等，
直到不等，記下字符符合條件的字符個數。最大的個數即為所求。(此方法適合如google這樣的字符串)
方法二：思路和方法一時一樣的，適合ggoggle這樣的字符串。
方法三：滿足題意，適合任何類型的字符串。就是時間復雜度為O(n^2)。
方法一
int counterplan1(conststring str)
{
int strlen=str.length();
int maxlen=0;
for(int i=0;i<strlen-1;i++)
{
if(str[i]==str[i+1])
{
int start=i-1;
int end=i+2;
while(start>0&& end<strlen)
{
if(str[start]==str[end])
{
--start;++end;
}else
{
break;
}
}
if(maxlen<end-start-1)
{
maxlen=end-start-1;
}
}
}
return maxlen;
}
方法二
int counterplan2(conststring str)
{
int strlen=str.length();
int maxlen=0;
for(int i=1;i<strlen-1;i++)
{
if(str[i-1]==str[i+1])
{
int start=i-1;
int end=i+2;
while(start>0&& end<strlen)
{
if(str[start]==str[end])
{
--start;++end;
}else
{
break;
}
}
if(maxlen<end-start)
{
maxlen=end-start;
}
}
}
return maxlen ;
}
方法三
int counterplan3(conststring str)
{
int strlen=str.length();
int maxlen=0;
int start=0,end=strlen-1;
while(start<end)
{
if(str[start]!=str[end])
{
if(start==end)
{
++start;
end=strlen-1;
}else{
--end;
continue;
}
}
int i=start,j=end;
bool isOK=false;
while(i<j &&!isOK){
while(str[++i]==str[--j])
{
if(i<j-2)
{
continue;
}
if(end-start+1>maxlen)
{
maxlen=end-start+1;
}
isOK=true;
break;
}
i=++start;j=end;
}
if(strlen-start<=maxlen-1)
{
break;
}
}
return maxlen ;
}
浙公網安備 33010602011771號