Valid Palindrome
Problem Description
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 * 105
- s consists only of printable ASCII characters.
Solve it on LeetCode
Approaches
1. Two-pointer: Clean String
Intuition:
The problem requires us to determine if a given string is a palindrome, considering only alphanumeric characters and ignoring cases. The basic idea is to first clean the string by removing all non-alphanumeric characters and converting everything to a consistent case (lowercase). Then, use two pointers to compare characters from the start and end of the string moving inwards.
Steps:
- Create a cleaned version of the string that contains only lowercase alphanumeric characters.
- Initialize two pointers, one at the start and another at the end of the cleaned string.
- Increment and decrement the pointers towards the center, checking if the characters are the same.
- If you reach the center with all characters matching, the string is a palindrome.
Code:
- Time Complexity: O(n), where n is the length of the input string. We traverse each character twice in the worst case (once for cleaning and once for palindrome checking).
- Space Complexity: O(n) for the cleaned buffer.
2. Two-pointers: O(1) space
Intuition:
The previous solution effectively checks the palindrome by cleaning up the string first. However, we can optimize it to not require extra space for a cleaned version. Instead, directly use two pointers on the input string to perform the checking while skipping over non-alphanumeric characters.
Steps:
- Initialize two pointers, left at the start and right at the end of the string.
- While left is less than right:
- Increment the left pointer until an alphanumeric character is found.
- Decrement the right pointer until an alphanumeric character is found.
- Compare the characters. If they are not equal, the string is not a palindrome.
- Move the pointers inward and repeat.
- If the entire string is processed without mismatches, it is a palindrome.
Code:
- Time Complexity: O(n), where n is the length of the input string. We traverse each character at most twice.
- Space Complexity: O(1), no additional space is used beyond integer indices.