Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
Constraints:
1 <= s.length <= 2 * 10^5
s consists only of printable ASCII characters.
My Solution
We can solve this problem with the two pointer technique. We first convert the string to lowercase. We then set pointers at the start of the string and at the end. We skip all characters that are not alphanumeric and compare each alphanumeric character at the two pointers.
Time complexity would be O(n) to convert the string to lowercase as well as scanning the string with two pointers. Space complexity would be O(1) since we require only constant extra space.
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int n = s.length();
int i = 0;
int j = n-1;
while (i < n && !Character.isLetterOrDigit(s.charAt(i))) {
i++;
}
while (j >= 0 && !Character.isLetterOrDigit(s.charAt(j))) {
j--;
}
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
while (i < n && !Character.isLetterOrDigit(s.charAt(i))) {
i++;
}
j--;
while (j >= 0 && !Character.isLetterOrDigit(s.charAt(j))) {
j--;
}
}
return true;
}
}