Given a non-empty string
s, you may delete at most one character. Judge whether you can make it a palindrome.
Input: "aba" Output: True
Input: "abca" Output: True Explanation: You could delete the character 'c'.
Intuition and Algorithm\n
For each index
i in the given string, let\'s remove that character, then check if the resulting string is a palindrome. If it is, (or if the original string was a palindrome), then we\'ll return
Time Complexity: where is the length of the string. We do the following times: create a string of length and iterate over it.\n
Space Complexity: , the space used by our candidate answer.\n
If the beginning and end characters of a string are the same (ie.
s == s[s.length - 1]), then whether the inner characters are a palindrome (
s, s, ..., s[s.length - 2]) uniquely determines whether the entire string is a palindrome.
Suppose we want to know whether
s[i], s[i+1], ..., s[j] form a palindrome. If
i >= j then we are done. If
s[i] == s[j] then we may take
i++; j--. Otherwise, the palindrome must be either
s[i+1], s[i+2], ..., s[j] or
s[i], s[i+1], ..., s[j-1], and we should check both cases.
Time Complexity: where is the length of the string. Each of two checks of whether some substring is a palindrome is .\n
Space Complexity: additional complexity. Only pointers were stored in memory.\n
Analysis written by: @awice\n