LeetCode 680. Valid Palindrome II

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:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Solution

English Version in Youtube

中文版解答Youtube Link

中文版解答Bilibili Link

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            if (s[i] != s[j]) {
                int i1 = i, j1 = j - 1, i2 = i + 1, j2 = j;
                while (i1 < j1 && s[i1] == s[j1]) {
                    i1++;
                    j1--;
                };
                if (i1 >= j1) {
                    return true;
                }
                while (i2 < j2 && s[i2] == s[j2]) {
                    i2++;
                    j2--;
                };
                if (i2 >= j2) {
                    return true;
                }
                
                return false;
            }
        }
        
        return true;
    }
};