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.

Problem Analysis:

Suppose str is a palindrome string, let index i = 0, index j = str.size()-1, so we compare str[i] and str[j], and iterate i++, j- -, we can verify it is palindrome because could not find str[i] != str[j].

If str is not a palindrome, but if delete a character in string, it can become palindrome. In this case, we still compare str[i] and str[j] as before. And we can find str[i] != str[j] when iterating. Then we can delete character at i or j, then continue to verify remaining string whether is palindrome. So we get it.

Solution:

class Solution {
public:
    bool validPalindrome(string s) {
        int start = 0;
        int end = s.size() - 1;
        while (start < end && s[start] == s[end]) {
            ++start;
            --end;
        }
        
        if (start >= end) return true;
        
        int i = start + 1;
        int j = end;
        while (i < j && s[i] == s[j]) {
            ++i;
            --j;
        }
        
        if (i >= j) return true;
        
        i = start;
        j = end - 1;
        while (i < j && s[i] == s[j]) {
            ++i;
            --j;
        }
                
        return i >= j;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)