华师一附中OI组

标题: 回文串的判断 [打印本页]

---

作者: admin    时间: 2018-5-18 19:03
标题: 回文串的判断
常见的有有两种方法：一种是把这个字符串颠倒，然后判断和原来的串是否相同

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. 
   
7.         if (s[0]!=s[l-1]) return 0;
   
8.         else
   
9.         {
   
10.             string ss=s.substr(1,l-2);
    
11.             return r3(ss);
    
12.         }
    
13. 
    
14. }

复制代码

---

作者: admin    时间: 2018-5-25 20:16
原地比较的绝妙做法

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. }

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2