问题描述:给定一个字符串,如何判断这个字符串是否是回文串?
解法一:两头向中间扫
给定一个字符串,定义两个分别指向字符串的头和尾的指针,然后让这两个指针都往字符串的中间扫描,在扫描的过程中,如果头和尾所指的字符从始至终都一样,那么该字符串为回文串。
参考代码:
#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来完成。分别将字符串放入栈中和队列中。利用两者的各自特点,只需要比较每次出栈字符和每次出队列的字符是否相同,如果当栈和队列剩余的元素等于长度一半时,对应的字符均相同,那么说明为回文的。
原文链接: https://www.cnblogs.com/zpfbuaa/p/5334201.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231088
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!