We’ll Solve Leetcode Problem: 125 Valid Palindrome

George Gognadze Tech Tips March 9, 2023 8 min read

Tags

To check if any given string is a palindrome or not, we just need to reverse it, and if the reversed string is the same as the original, then it is a palindrome. In this case, we have to ignore all the characters except alphanumeric ones.

If we reverse the word “anabana” we still get “anabana”; the same thing happens if we reverse the string “ai ia”. But what if we reverse “travel”? In this case, we get “levart” and it’s clearly not the same in reverse, so that means that this string is not a palindrome.

To solve this problem using built-in JavaScript functions, we write this code:

Copy Code

function isPalindrome(s) {
    // Convert to lowercase and remove non-alphanumeric characters
    s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    // Check if the reversed string is the same as the original
    return s === s.split('').reverse().join('');
    }

See less

The ‘isPalindrome’ function takes a string ‘s’ as input.
It first converts the string to lowercase using the ‘toLowerCase’ method.
It then removes all non-alphanumeric characters from the string using a regular expression and the ‘replace’ method.
It checks if the reversed string is the same as the original string by splitting the string into an array of characters, reversing the array, and then joining the array back into a string using the ‘split’, ‘reverse’, and ‘join’ methods.
If the reversed string is the same as the original string, the function returns ‘true’, otherwise it returns ‘false’.

Copy Code

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
    console.log(isPalindrome("race a car")); // false
    console.log(isPalindrome(" ")); // true

See less

Instead of using a regular expression to remove non-alphanumeric characters, you can use ‘charCodeAt()’ to check if a character is alphanumeric. This can be faster than using a regular expression.

You can avoid creating a new array and new string to check for palindrome by using two pointers that start at the beginning and end of the string and move towards each other. This reduces the amount of memory used by the function.

Copy Code

function isPalindrome(s) {
    // Initialize pointers
    let left = 0;
    let right = s.length - 1;
 
    // Loop until pointers meet
    while (left < right) {
    // If left pointer is not alphanumeric, move right
    if (!isAlphanumeric(s.charCodeAt(left))) {
    left++;
    continue;
    }
 
    // If right pointer is not alphanumeric, move left
    if (!isAlphanumeric(s.charCodeAt(right))) {
    right--;
    continue;
    }
 
    // Compare characters at both pointers (case insensitive)
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
    return false;
    }
 
    // Move pointers inward
    left++;
    right--;
    }
 
    // If pointers have met, the string is a palindrome
    return true;
    }
 
    function isAlphanumeric(code) {
    return (code >= 48 && code <= 57) || // 0-9
    (code >= 65 && code <= 90) || // A-Z
    (code >= 97 && code <= 122); // a-z
    }

See less

Here’s how the optimizations work:

The ‘isAlphanumeric’ function takes a character code and returns ‘true’ if the character is alphanumeric. This function is called in the main ‘isPalindrome’ function to check if a character is alphanumeric.
The ‘isPalindrome’ function uses two pointers (left and right) that start at the beginning and end of the string, respectively. The function then loops until the pointers meet.
At each iteration of the loop, the function checks if the character at the left pointer and right pointer is alphanumeric. If either pointer is not alphanumeric, the pointer is moved towards the center of the string.
If both pointers are alphanumeric, the function compares the characters at both pointers (ignoring case). If the characters do not match, the function returns false.
If the pointers meet, the function returns ‘true’, indicating that the string is a palindrome.

This optimized code reduces the number of operations and the amount of memory used by the function, making it faster and more efficient than the original code.

The time complexity of the optimized solution is O(n), where n is the length of the input string. This is because the function traverses the string only once and does a constant amount of work for each character in the string.

In contrast, the time complexity of the original solution is O(n + n + n), which simplifies to O(n). This is because the function creates a new string and a new array of characters, both of which have a length of n, and then performs a reverse operation that takes O(n) time. However, this solution requires more memory and can be slower due to the overhead of creating and manipulating new objects.

Therefore, the optimized solution that uses two pointers to traverse the string and avoids creating new strings or arrays will be faster for very long strings and is generally a better approach for this problem.

The space complexity of the original solution that creates a new string and a new array of characters is O(n), where n is the length of the input string. This is because the function creates a new string and array of characters with a length of n, which requires O(n) space.

The space complexity of the optimized solution that uses two pointers is O(1), which is constant space. This is because the function does not create any new data structures and only uses a constant amount of space for the pointers and other variables that are created.

Finally, let’s remember that to solve this problem, we should use the optimized solution that uses two pointers which is more space-efficient and is generally a better approach.

Was this article useful for you?

Get in the know with our publications, including the latest expert blogs

End-to-End Digital Transformation

Reach out to our experts to discuss how we can elevate your business

Learn more