【回文串14】LeetCode 680. Valid Palindrome II-CSDN博客

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/80500572

LeetCode 680. Valid Palindrome II

Solution1：我的答案
复杂度是 $O(n)$ ，不算好啊。。
注意：对于c++中string对象常用的insert()和erase()操作，记录如下，摘抄自《C++ Primer (第五版)》P323

操作	说明
s.insert(pos, args)	在pos之前插入args指定的字符。pos可以是一个下标或一个迭代器。接受下标的版本返回一个指向s的引用；接受迭代器的版本返回指向第一个插入字符的迭代器。
s.erase(pos, args)	删除从位置pos开始的len个字符。如果len被省略，则删除从位置pos开始至s末尾的所有字符。返回一个指向s的引用

class Solution {
public:
    bool validPalindrome(string s) {
        int n = s.size();
        if (n <= 2) return true;
        int i = 0, j = n - 1;
        while (i < j) {
            if (s[i] == s[j]) {
                i++;j--;
            }
            else {
                string s1 = s;//执行完一个删除操作后，原字符串会改变
                return (my_validPalin(s.erase(i, 1)) 
                       || my_validPalin(s1.erase(j, 1)));
            }
        }
        return true;
    }

    bool my_validPalin(string &s) {
        int n = s.size();
        if (n <= 1) return true;
        int i = 0, j = n - 1;
        while (i < j) {
            if (s[i] == s[j]) {
                i++;j--;
            }
            else
                return false;
        }
        return true;
    }
};