Valid Palindrome
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.
Can you come up with a solution that achieves O(n) time complexity?
Can you come up with a solution that achieves O(1) space complexity?
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.
def is_palindrome(s: str) -> bool:
# Filter out non-alphanumeric characters and convert to lowercase
filtered_chars = [char.lower() for char in s if char.isalnum()]
# Check if the filtered string reads the same forward and backward
return filtered_chars == filtered_chars[::-1]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.
def is_palindrome(s: str) -> bool:
# Initialize two pointers
left, right = 0, len(s) - 1
while left < right:
# Move left pointer to the next alphanumeric character
while left < right and not s[left].isalnum():
left += 1
# Move right pointer to the previous alphanumeric character
while left < right and not s[right].isalnum():
right -= 1
# Compare characters at left and right pointers
if s[left].lower() != s[right].lower():
return False
# Move both pointers towards the center
left += 1
right -= 1
return TrueTime 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.
Check out our lesson on the two-pointer approach to learn more about it and its applications!
public static boolean isPalindrome(String str){ boolean flag = true; int len = str.length()-1; int j = len;
for(int i=0;i<=len/2;i++){ if(str.charAt(i)!=str.charAt(j--)){ flag = false; break; } } return flag; }