问题描述：给定一个字符串，如何判断这个字符串是否是回文串？
解法一：两头向中间扫
给定一个字符串，定义两个分别指向字符串的头和尾的指针，然后让这两个指针都往字符串的中间扫描，在扫描的过程中，如果头和尾所指的字符从始至终都一样，那么该字符串为回文串。
参考代码：
#include <bits/stdc++.h> using namespace std; bool IsPalindrome( char *s , int n ) { //illegal input if( s == NULL || n < 1 ) return false; char *front, *back; front = s; back = s + n - 1; while( front < back ) { if( *front != *back) { return false; } ++front; --back; } return true; } int main() { char *s[3][1]; s[0][0] = "mom"; s[1][0] = "dad"; s[2][0] = "child"; int lens[3]; lens[0] = strlen(s[0][0]); lens[1] = strlen(s[1][0]); lens[2] = strlen(s[2][0]); for(int i = 0 ; i < 3 ; i ++ ) { if(IsPalindrome(s[i][0],lens[i])) cout<<s[i][0]<<" is palindrome"<<endl; else cout<<s[i][0]<<" isn't palindrome"<<endl; } }
GCC运行结果：
解法二：从中间往两头扫
参考第一种方法，将指针移动到字符串的中间，从中间进行扫描，同时判断对应字符是否相等。
参考代码：
#include <bits/stdc++.h> using namespace std; bool IsPalindrome( char *s , int n )//n为字符串的长度 { //illegal input if( s == NULL || n < 1) { return false; } char *first , *second; //find the mid index int m = ( ( n >> 1 ) - 1 ) >=0 ? ( n >> 1 ) - 1 : 0; //move first and second pointer to mid first = s + m; second = s + n - 1 - m; while( first >= s) { if( *first != *second) { return false; } //mind this move --first; ++second; } return true; } int main() { char *s[3][1]; s[0][0] = "mom"; s[1][0] = "dad"; s[2][0] = "child"; int lens[3]; lens[0] = strlen(s[0][0]); lens[1] = strlen(s[1][0]); lens[2] = strlen(s[2][0]); for(int i = 0 ; i < 3 ; i ++ ) { if(IsPalindrome(s[i][0],lens[i])) cout<<s[i][0]<<" is palindrome"<<endl; else cout<<s[i][0]<<" isn't palindrome"<<endl; } return 0; }
GCC运行结果：
举一反三：
（1）链表回文
判断一条单向链表时不时回文
容易想到的思路是采用两个指针从两边或者中间开始遍历，并判断对应的字符是否相等。但由于单链表是单向的，如何实现双向便利？比较常见的思路：采用经典的快慢指针方法，可以先定位到链表的中间位置，再将链表的后半段逆置（可以递归实现逆置），然后用两个指针同时从链表的头部和中间逐一向后遍历。
（2）栈回文
判断一个栈是不是回文
根据栈的特性（FILO）first in last out ,可以将字符串压入栈中，再依次将每个字符出栈，从而得到原字符串的逆置串，将逆置串的各个字符分别和原字符串的各个字符进行比较，如果完全一致，则为回文串。
也可以借助队列（FIFO）first in first out来完成。分别将字符串放入栈中和队列中。利用两者的各自特点，只需要比较每次出栈字符和每次出队列的字符是否相同，如果当栈和队列剩余的元素等于长度一半时，对应的字符均相同，那么说明为回文的。