经典算法题--求对策字符串的最大长度(第二版)-阿里云开发者社区

开发者社区> 人工智能> 正文

经典算法题--求对策字符串的最大长度(第二版)

简介:

经典算法题--求对策字符串的最大长度(第二版)

 方法一:思路很中规中矩,遍历这个字符串,若有发现相邻的两个字符相等,就循环判断与这两个字符相邻的两个字符是否相等,
         直到不等,记下字符符合条件的字符个数。最大的个数即为所求。(此方法适合如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 ;
}
复制代码

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章