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: After removing non-alphanumeric, it becomes ""
Empty string is a palindrome
Use two pointers starting from both ends and move towards center. Skip non-alphanumeric characters and compare alphanumeric characters (case-insensitive).
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric from left
while left < right and not s[left].isalnum():
left += 1
# Skip non-alphanumeric from right
while left < right and not s[right].isalnum():
right -= 1
# Compare characters (case-insensitive)
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
def isPalindrome(s):
# Clean string: keep only alphanumeric and lowercase
cleaned = ''.join(c.lower() for c in s if c.isalnum())
# Check if palindrome
return cleaned == cleaned[::-1]
Time: O(n), Space: O(n) for cleaned string
Two pointers is preferred for interviews to demonstrate space optimization.
1/**
2 * Valid Palindrome
3 * Time: O(n)
4 * Space: O(1) with two pointers, O(n) with string cleaning
5 */
6
7// Approach 1: Two Pointers (Optimal - O(1) space)
8class Solution {
9 public boolean isPalindrome(String s) {
10 int left = 0, right = s.length() - 1;
11
12 while (left < right) {
13 // Skip non-alphanumeric from left
14 while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
15 left++;
16 }
17
18 // Skip non-alphanumeric from right
19 while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
20 right--;
21 }
22
23 // Compare characters (case-insensitive)
24 if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
25 return false;
26 }
27
28 left++;
29 right--;
30 }
31
32 return true;
33 }
34}
35
36// Approach 2: Clean String First (O(n) space)
37class Solution2 {
38 public boolean isPalindrome(String s) {
39 // Clean string: keep only alphanumeric and lowercase
40 StringBuilder cleaned = new StringBuilder();
41 for (char c : s.toCharArray()) {
42 if (Character.isLetterOrDigit(c)) {
43 cleaned.append(Character.toLowerCase(c));
44 }
45 }
46
47 // Check if palindrome
48 String str = cleaned.toString();
49 return str.equals(new StringBuilder(str).reverse().toString());
50 }
51}
52