Solution
We’ll employ the standard two pointer approach for palindrome checking. Let i start from beginning of the word and j from end of the word. As long as character at i and character at j are equal, increment i and decrement j. If they are unequal, we have the following cases:
- Delete character at i and check if the word from i+1 to j is a palindrome or
- Delete character at j and check if the word from i to j-1 is a palindrome
bool validPalindrome(string s) {
int len = s.length();
for (int i=0, j=len-1; i<j; i++, j--) {
if (s[i] == s[j])
continue;
return isPalindrome(s, i+1, j) || isPalindrome(s, i, j-1);
}
return true;
}
bool isPalindrome(string s, int start, int end) {
while (start<end) {
if (s[start] != s[end])
return false;
start++;
end--;
}
return true;
}
Time complexity: O(n)