Reference: 125. Valid Palindrome & 680. Valid Palindrome II EPI 6.5
Difficulty: Easy

Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example:

Follow up: Do not use extra space. Also, check out Valid Palindrome II section.

Analysis

Brute-Force

The basic idea is based on the following code:

Since the input has some non-alphanumeric characters, we have to do some preprocessing.

• Remove invalid characters (Character.isLetterOrDigit(ch)).
• Convert all letters to lower cases (use s.toLowerCase()).
• Reversing is optional (it also incurs extra space usage).

Note:

• Since the StringBuilder is resizable, the condition in while-loop is idx < sb.length() instead of idx < n.
• Remember to update the length n after preprocessing.

Time: $O(N)$
Space: $O(N)$

Two Pointers

We use two indices (pointers) to traverse the string, one forwards, the other backwards, skipping nonalphanumeric characters, performing case-insensitive comparison on the alphanumeric characters. We return false as soon as there is a mismatch. If the indices cross, we have a verified palindrome string.

Note: Remember to update lo and hi at the end of each iteration.

Time: $O(N)$
Space: $O(1)$

Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. In other words, we allow one mismatch.

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

Example:

Brute-Force

Delete each character and then test palindromicity.

Time: $O(N^2)$
Space: $O(1)$

SubPalindrome (Iteration)

When detecting the first mismatch we should consider two cases:

• Case 1: Delete the character on the left, and move on.
• Case 2: Delete the character on the right, and move on.

Then we get rid of the characters we have checked before, and only focus on those substrings in two cases. If the first case fails, we will try the second case. If it also fails, return false.

Notice that when a mismatch is detected in for-loop, every future work would be done within the current iteration.

Show me the code:

Time: $O(N)$ since there are at most $\sim 2N$ operations.
Space: $O(1)$

SubPalindrome (Recursion)

Based on the idea above, we can write a recursive version.

Note: You have to pass down a used variable to indicate if the remedy has been used.

Time: $O(N)$
Space: $O(N)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.