leetcode 680. Valid Palindrome II

ゞ浴缸里的玫瑰 2022-06-08 07:46 119阅读 0赞

# 1.题目 #

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.  
给一个非空字符串，最多只允许删除一个字符。判断是否能让这个字符串回文。  
Example 1:  
Input: “aba”  
Output: True  
Example 2:  
Input: “abca”  
Output: True  
Explanation: You could delete the character ‘c’.

# 2.分析 #

从两端向中间遍历字符串，当遇到左右两端字符不相等时，有两种删除的可能：  
删除左边的字符 or 删除右边的字符  
对这两种情况再判断是否回文即可。

# 3.代码 #

方法1：

class Solution {
    public:
        bool validPalindrome(string s) {
            int c1 = 0, c2 = 0;
            int l = 0, r = s.size() - 1;
            while (l < r) {
                if (s[l] != s[r])
                {
                    ++l;//删除左边的字符
                    c1 += 1;
                }
                else {
                    ++l;
                    --r;
                }
            }
            l = 0, r = s.size() - 1;
            while (l < r) {
                if (s[l] != s[r]) {
                    --r;//删除右边的字符
                    c2 += 1;
                }
                else {
                    ++l;
                    --r;
                }
            }
            return c1 < 2 || c2 < 2;
        }
    };

方法2：

class Solution {
    public:
        bool isPalindroms(string s,int l,int r) {
            while (++l < --r) {
                if (s[l] != s[r])
                    return false;
            }
            return true;
        }
        bool validPalindrome(string s) {
            if (s.size() < 2)
                return true;
            int l = -1, r = s.size();
            while (++l < --r) {
                if (s[l] != s[r])
                    return isPalindroms(s, l, r+1) || isPalindroms(s, l-1, r);
            }
            return true;
        }
    };