Valid Palindrome

leet code problem 125

Problem statement

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.

Solution 1

1. define a regular expression regexp that matches any alphanumeric character (letters and numbers).
2. initialize two empty strings, newString and reversed, to store the processed input string and its reverse, respectively.
3. loop through each character char in the input string s.
4. For each character, check if it matches the regular expression regexp using the test() method. This ensures you only consider alphanumeric characters.
5. If the character is alphanumeric, you add the lowercase version of the character to newString, and you add the lowercase version of the character to the beginning of reversed.

  /* 
#PLAN

- use regex to get a new string that consists
only the alphanumeric characters
- check the new string with its inverce 
- if they are equal return true
*/
var isPalindrome = function(s) {
    let regexp = /^[A-Za-z0-9]+$/;
    let newString=""
    let reversed="";
    for(let char of s){
     if (regexp.test(char)){
          newString += char.toLowerCase();
          reversed= char.toLowerCase() + reversed;
     }
   
    }
    console.log(newString, reversed)
    if(newString===reversed){
        return true;
    }else{
        return false
    }

};

Solution 2

 var isPalindrome = function(s) {
    // Remove all non-alphanumeric characters and convert to lowercase
    let processedString = s.replace(/[^A-Za-z0-9]/g, '').toLowerCase();
    
    // Iterate through the string and compare characters from the start and end
    let left = 0;
    let right = processedString.length - 1;
    
    while (left < right) {
        if (processedString[left] !== processedString[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;

};

Here's how the code works:

1. First, we use a regular expression to remove all non-alphanumeric characters from the input string s, and then convert all the remaining characters to lowercase. This gives us the processedString.
2. We then initialize two pointers, left and right, to the start and end of the processedString, respectively.
3. We iterate through the processedString, comparing the characters from the start and end. If any pair of characters does not match, we return false.

If we've checked all the characters and they all match, we return true, indicating that the string is a palindrome. The time complexity of this solution is O(n), where n is the length of the input string s, as we need to iterate through the entire string once. The space complexity is O(n) as well, since we create a new string processedString to hold the processed version of the input string.