680. Valid Palindrome II
1. Description
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
2. Example
Example 1:
Input: “aba”
Output: True
Example 2:
Input: “abca”
Output: True
Explanation: You could delete the character ‘c’.
3. Constraints
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
4. Solutions
My Accepted Solution
n = i_str.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
private:
bool isPalindrome(string &i_str, int left, int right)
{
for( ;left < right; left++, right--)
{
if(i_str[left] != i_str[right])
return false;
}
return true;
}
public:
// bool validPalindrome(string s)
bool validPalindrome(string &i_str)
{
for(int left = 0, right = i_str.size() - 1; left < right; left++, right--)
{
if(i_str[left] != i_str[right])
{
return isPalindrome(i_str, left + 1, right) || isPalindrome(i_str, left, right - 1);
}
}
return true;
}
};