Back to Two Pointers
Easy
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.
Examples
Input:s = "A man, a plan, a canal: Panama"
Output:true
"amanaplanacanalpanama" is a palindrome.
Input:s = "race a car"
Output:false
"raceacar" is not a palindrome.
Constraints
1 <= s.length <= 2 * 10^5s consists only of printable ASCII characters.
Approach
Create a new string by filtering out all non-alphanumeric characters and converting them to lowercase. Then, create a reversed version of this new string and compare the two. If they are identical, the original string is a valid palindrome.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
This approach requires O(n) extra space to store the filtered and reversed strings.
Solution.java
class Solution { public boolean isPalindrome(String s) { StringBuilder filtered = new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) { filtered.append(Character.toLowerCase(c)); } } String original = filtered.toString(); String reversed = filtered.reverse().toString(); return original.equals(reversed); }}