一、反向扫描
（1）、判断回文串
bool check(string &s, int left, int right)
{
int i=left,j=right;
while(i<j)
{
if(s[i]!=s[j])
{
return false;
}
i++;
j--;
}
return true;
}1、有效回文串
描述 给定一个字符串，判断其是否为一个回文串。只考虑字母和数字，并忽略大小写。 输入: "A man, a plan, a canal: Panama" 输出: true
isalnum(int c):判断c是否为字母或数字 tolower(int c):将字母转成小写，如果c就是数字则不改变
class Solution {
public:
bool isPalindrome(string &s) {
// write your code here
int i=0,j=s.length()-1;
bool flag=true;
while(i<j)
{
while(i<j && !isalnum(s[i]))
{
i++;// 忽略前面的非数字
}
while(i<j && !isalnum(s[j]))
{
j--;
}
if(i<j)
{
if(tolower(s[i])!=tolower(s[j]))
{
flag=false;
break;
}
}
i++;// 移动指针
j--;
}
return flag;
}
};2、至多删除一个字符，使其为回文串
描述 给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。 给定的字符串只包含小写字母 字符串的长度最大为 50000
不需要实际地将字符删除，只需要检查s是否为回文串时，将其“过滤”掉
s="abbcba"
首先 ab 和 ba 能够组成回文串
此时 left=2,指向第2个b，right=3，指向c
再看s(2+1,3)，即b ，s(2,3-1)即c是否为回文串，即过滤掉了c或者b
因为内部的子串是回文串，外部的也是回文串，所以整个s也是回文串（删除了中间的b或c）class Solution {
public:
// 检查 s 的子串(left,right)是否为回文串
bool check(string &s, int left, int right)
{
int i=left,j=right;
while(i<j)
{
if(s[i]!=s[j])
{
return false;
}
i++;
j--;
}
return true;
}
bool validPalindrome(string &s) {
// Write your code here
int i=0,j=s.length()-1;
while(i<j)
{
if(s[i]==s[j])
{
i++;
j--;
}else
{
return check(s,i+1,j) || check(s,i,j-1);
}
}
return true;
}
};