尺取法例题C++

一、反向扫描

（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;
    }
};

二、同向扫描