Is this a valid palindrome?
Easy
Given a string s, return true if it is a palindrome, and false otherwise. A string is considered a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Write a function isPalindrome that implements this logic.
Examples
Input: s = "H123!@321h" Output: true Input: s = "race a car" Output: false
Constraints
1 <= s.length <= 2 * 10^5- The input string
scan include any printable ASCII characters.
Solution 1: Filtering and Reversing Approach
This solution processes the input string by first filtering out non-alphanumeric characters and converting all remaining characters to lowercase. It then checks if this filtered string reads the same forward and backward.
- Filtering: Iterate through the string and collect alphanumeric characters while converting them to lowercase.
- Reversing and Comparing: Create a reversed version of the filtered string and compare it with the original filtered string to check for palindrome properties.
Time Complexity: The time complexity is O(n), where n is the length of the input string. This is because filtering the characters and creating the reversed string both require iterating through the input once.
Space Complexity: The space complexity is O(n) for storing the filtered characters and their reversed copy. This space is needed to hold the filtered string and its reversed version.
Solution 2: Two-Pointer Approach
This solution uses a two-pointer technique to efficiently check if the string is a palindrome. The idea is to use one pointer starting from the beginning of the string (left) and another pointer from the end (right). The pointers move towards each other, skipping non-alphanumeric characters and comparing characters that are alphanumeric.
- Pointer Initialization: Set two pointers:
leftat the beginning andrightat the end of the string. - Skipping Non-Alphanumeric Characters: Move the
leftpointer to the right while skipping non-alphanumeric characters, and similarly move therightpointer to the left. - Comparison: Compare the characters at
leftandrightin a case-insensitive manner. If characters do not match, the string is not a palindrome. - Update Pointers: Move the pointers closer to each other and repeat until the pointers meet or cross.
Time Complexity: The time complexity is O(n), where n is the length of the string. Each character is processed at most twice (once by each pointer).
Space Complexity: The space complexity is O(1) as it only uses a constant amount of extra space for the two pointers, regardless of the size of the input string.
Interview experiences
4 sharedRelated courses
