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.