题解 | #验证回文字符串(二)#

class Solution {

public:

bool palindrome2(string str, int left, int right) {
    /*
    对删除元素后的字符串进行判断
    因为前面已经判断了，所以多设置left和right两个参数
    避免重复判断前面，导致耗时增加
    */
    while (left < right) {
        if (str[left] != str[right])
            return false;
        left++;
        right--;
    }
    return true;
}
bool palindrome(string str) {
    // write code here
    
    /*
    如果str长度为1或者2可以直接返回true
    一定能通过裁剪变成回文
    */
    
    if (str.length() == 1 || str.length() == 2) {
        return true;
    }
    /*
    定义首尾指针，指向字符串首尾
    */
    int left = 0;
    int right = str.length() - 1;
    
    /*
    开始首尾遍历
    查找不相同的字符
    找到后删除字符再判断
    如果没有返回true
    */
    
    while (left < right) {
        if (str[left] == str[right]) {
            left++;
            right--;
        } else {
        
            /*
            删除字符分为两种，删除left或者right
            所以复制一个str
            一个删除left判断
            一个删除right判断
            */
            
            string temp = str;
            
            /*
            因为删除了一个元素
            所以设置首尾指针时，
            被删除指针要后移（对尾指针来说是前移）
            erase()函数删除相应字符
            erase(int pos,int num)从pos开始删除num个字符
            erase(p)删除迭代器p指向的字符
            erase(first，last)删除迭代器first到last范围内的字符
            */
            
            return palindrome2(str.erase(left, 1), left - 1, right) ||
                   palindrome2(temp.erase(right, 1), left, right - 1);
        }
    }
    return true;
}

};