AlgoDaily - Validate Palindrome - One Pager Cheat Sheet

One Pager Cheat Sheet

You can write a method using O(n) time and O(1) space complexity to check if a given string of length 100000 or less is a palindrome, taking into account non-alphanumerical characters.
The given string is a palindrome if it reads the same forwards as it does backwards.
With built-in methods, you can easily reverse() or [::-1] a String and then compare it to the original to check if it is a palindrome.
By utilizing two variables, low and high, to represent the starting and ending indices of a string to be checked, and using a while loop to compare characters at these indices, we can determine if a string is a palindrome or not.
The code reverses a string by looping over the characters, swapping the characters and keeping track of the start and end indexes using a temp variable, and then joining the characters of the str_copy list to return the reversed string.
We can reduce complexity by using two pointers instead of one and only have to do len(str)/2 iterations of the while loop in order to validate if a string is a palindrome.
Comparing characters of a string with two pointers, start pointing to the beginning and end pointing to the last character, the example input racecar shows us the initial comparisons.
The runtime of the code is O(n), with O(1) space complexity, where n is the length of the string, since it iterates linearly with a constant space overhead.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx
}
 
var assert = require('assert');
​
function isPalindrome(str) {
  if (!str || str === '') {
    return true;
  } else {
    let left = 0;
    let right = str.length - 1;
    let leftChar;
    let rightChar;
​
    while (left < right) {
      leftChar = str.charAt(left).toLowerCase();
      rightChar = str.charAt(right).toLowerCase();
​
      if (isAlphaNumeric(leftChar) && isAlphaNumeric(rightChar)) {
        if (leftChar == rightChar) {
          left++;
          right--;
        } else {
          return false;
        }
      } else {
        if (!isAlphaNumeric(leftChar)) {
          left++;
        }
        if (!isAlphaNumeric(rightChar)) {
          right--;
        }
      }
    }
​

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.