华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1349|回复: 1
打印 上一主题 下一主题

回文串的判断

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-5-18 19:03:40 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
常见的有有两种方法:一种是把这个字符串颠倒,然后判断和原来的串是否相同
  1. bool r1(string s)
  2. {
  3.     string t="";
  4.     for (i=0;i<=s.size()-1;i++)  t=t+s[i]; ///颠倒
  5.     return s==t;
  6. }
复制代码


第二种是直接原地比较,看第一位是否等于最后一位,第二位是否等于倒数第二位,这又有两种做法,第一种是用两个指针分别指着头和尾,一个加一个减的比较。
  1. bool r2(string s)
  2. {
  3.     int i=0,j=s.size()-1;
  4.     bool b=1;
  5.     while (b && i<j)
  6.         if (s[i]!=s[j]) b=0;
  7.         else
  8.         {
  9.             i++;
  10.             j--;
  11.         }
  12.     return b;
  13. }
复制代码



另外一种就是递归。

  1. bool r3(string s)
  2. {
  3.     int l=s.size();
  4.     if (l<=1) return 1;
  5.     else

  6.         if (s[0]!=s[l-1]) return 0;
  7.         else
  8.         {
  9.             string ss=s.substr(1,l-2);
  10.             return r3(ss);
  11.         }

  12. }
复制代码


回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 2018-5-25 20:16:44 | 只看该作者
原地比较的绝妙做法
  1. bool r4(string s)
  2. {
  3.     bool b=1;
  4.     for (int i=0,j=s.size()-1; b && i<j; i++,j--)
  5.         if (s[i]!=s[j]) b=0;
  6.     return b;
  7. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 03:10 , Processed in 0.110520 second(s), 22 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表