leetcode 680. Valid Palindrome II 去除一个字符的回文字符串判断 + 双指针

落日映苍穹つ 2022-06-03 08:26 138阅读 0赞

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’.  
Note:  
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

本题题意很简单，要是直接暴力的删除字符会超时，所以直接跳过即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool validPalindrome(string s) 
        {
            int left = 0, right = s.length() - 1;
            while (left < right)
            {
                if (s[left] == s[right])
                {
                    left++;
                    right--;
                }
                else
                {
                    return isPalindrome(s, left, right - 1) || isPalindrome(s, left + 1, right);
                }
            }
            return true;
        }
    
        bool isPalindrome(string s,int left,int right)
        {
            while (left < right)
            {
                if (s[left] == s[right])
                {
                    left++;
                    right--;
                }
                else
                    return false;
            }
            return true;
        }
    };