Leetcode - Valid Palindrome (with JavaScript)

Today I am going to show how to solve the Valid Palindrome algorithm problem.

Here is the problem:

Let’s take a simple example and determine whether or not this string is a palindrome. A palindrome is a string that's written the same forward as backward.

"abcdcba"

There are several ways to solve it. First, I’ll look at the simplest and most straightforward ways.

We can build up a new string (newString += s[i]) that is going to be the reversed version of our input string. We then compare that new string to the input string to see if they are equal to each other. If they are equal, it means our input string is a palindrome.

This solution will give us O(N) space and O(n^2) time complexity. We can improve the time complexity from O(n^2) to O(n) by using an array.

Instead of creating a new string, we can just store everything in an array. Then at the end, we can join all the elements of the array into one string and then do the comparison to determine if the string is a palindrome.

We can improve this solution by iterating through the string and using pointers.

We can start with a pointer on the first letter and a pointer on the last letter. Then we compare the two. If they are equal to each other, we keep moving the pointers to the next letters until the pointers overlap. Then we return true, indicating that the string is indeed a palindrome. If they are not equal to each other, then we return false.

var isPalindrome = function(s) {

    let leftIdx = 0;
    let rightIdx = s.length - 1;

    while(leftIdx < rightIdx){
        if (s[leftIdx] !== s[rightIdx]) return false

        rightIdx --
        leftIdx ++ 

    }
    return true
};

What do we do if a string has spaces or other symbols in it?

"A man, a plan, a canal: Panama"

There is no inbuilt method in Javascript to determine if the specified character is a letter or digit. We could build a helper method to pass the string through. But I am going to use a different approach. Before iterating through the string, I am going to remove all spaces and symbols. by using the replace() method with regex. It takes two parameters, the string to be replaced and the string we are replacing it with.

NOTE: https://regexr.com/ is a good resource for learning and practicing regex expressions.

var isPalindrome = function(s) {
    s = s.replace(/[^a-zA-Z0-9]/g,"").toLowerCase();

    let leftIdx = 0;
    let rightIdx = s.length - 1;

    while(leftIdx < rightIdx){
        if (s[leftIdx] !== s[rightIdx]) return false

        rightIdx --
        leftIdx ++ 

    }
    return true
};