Skip to main content

Valid Palindrome Solution

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.

Examples​

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Constraints​

  • 1≤s.length≤2×1051 \leq s.length \leq 2 \times 105

Solution for Valid Palindrome Problem​

Approach 1: Brute Force​

Intuition​

The brute force approach involves stripping non-alphanumeric characters from the string and then checking if the resulting string is a palindrome by comparing it with its reverse.

Implementation​

Code in Different Languages​

// JAVA

class Solution {
public boolean isPalindrome(String s) {
String str = s.toLowerCase();
str = str.replaceAll("\\s",""); // remove all space in string
str = str.replaceAll("[^a-z0-9]",""); // remove all non-alphanumerical
int i=0,j=str.length()-1;
while(i<j){
char ch = str.charAt(i);
char ch1 = str.charAt(j);
if(ch==ch1){
i++;
j--;
}
else return false;
}
return true;
}
}

//Java-script

var isPalindrome = function(s){
let left = 0, right = s.length - 1;
while (left < right) {
if (!isAlphaNumeric(s[left]))
left++;
else if (!isAlphaNumeric(s[right]))
right--;
else if (s[left].toLowerCase() !== s[right].toLowerCase())
return false;
else {
left++;
right--;
}
}
return true;
}

function isAlphaNumeric(char) {
const code = char.charCodeAt(0);
return (code >= 48 && code <= 57) || (code >= 65 && code <= 90) || (code >= 97 && code <= 122);
}
//python

def is_palindrome(s: str) -> bool:
if not s:
return True
cleaned_s = ''.join(ch.lower() for ch in s if ch.isalnum())
return cleaned_s == cleaned_s[::-1]

input_str = "A man, a plan, a canal: Panama"
output = is_palindrome(input_str)

print("Input:", input_str)
print("Output:", output)

//java
class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.isEmpty()) {
return true;
}

String cleanedS = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
return cleanedS.equals(new StringBuilder(cleanedS).reverse().toString());
}
}
//cpp

class Solution {
public:
bool isPalindrome(string s) {
if (s.empty()) {
return true;
}

string cleanedS;
for (char ch : s) {
if (isalnum(ch)) {
cleanedS += tolower(ch);
}
}

string reversedS = cleanedS;
reverse(reversedS.begin(), reversedS.end());

return cleanedS == reversedS;
}
};

Complexity Analysis​

  • Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
  • Space Complexity: O(n), where n is the length of the input string. We create a new string to store the cleaned version of the input.

References​