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.
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.
Step 1 : – Template Implementation
There are two types of two pointer templates.
1). Opposite direction two pointer template
2). Same direction two pointer template
Based on our analysis of the problem statement, this is a non-target-based problem where we need to verify if the given string is a valid palindrome. Therefore, we will use the base structure of the opposite direction pointers template.
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
//code
left++;
right--;
}
return true;
}
}Step 2 : – Comparing two characters.
Convert both characters to lowercase using Character.toLowerCase() and compare them. If they differ, return false otherwise, continue moving the pointers until they meet.
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
// Compare characters ignoring case
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}Step 3 : – Skip non-alphanumeric characters
Move the pointers inward while ignoring any characters that are not letters or digits using Character.isLetterOrDigit().
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
// Skip non-alphanumeric characters
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
// Compare characters ignoring case
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}Final Code : –
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
// Skip non-alphanumeric characters
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
// Compare characters ignoring case
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}