Palindrome Check

Basic Solution

The first solution is intuitive and relies on the javascript's reverse(), split() and join() method.

1. Split the input string with "", so that every character will be a separate character in the array. Therefore, the string "race car" becomes ["r", "a", "c", "e", " ", "c", "a", "r"]
2. Use the javascript's native reverse() method to reverse the string.
3. Join back the array to form the string using join() method.
4. Compare the input string with the newly created string.
5. If the newly created string is equal to the given string, return true, else return false

Time Complexity

• O(n) because we reverse the given string.

Two Pointer Approach

• Declare two pointers, left and right. Initialize left = 0 and right = stringLength - 1.
• Run a while loop with the condition of left < right.
• Check if str[i] !== str[j]. If this is not the case, we can be sure that the strings are not palindrome. Because the extreme ends must be equal for a string to be a palindrome.
• Otherwise, Increment left AND decrement right.
• return true of while loop breaks.

Time Complexity

• O(n) - Because we iterate atleast the half of the array.

Recursive Approach

• Taking a recursive approach, everytime we are going to pass the i value in the palindromeCheck() function.
• We then compute the corresponding j value by str.length - 1 - i.
• The base case will be if (i >= j) - this means we've crossed OR are standing at the middle of the array and we return true;
• We then check if str[i] !== str[j] - Trying to check if the values at i and j are not equal. If they're not equal, return true
• Otherwise, we recurse with incrementing the i value by palindromeCheck(str, i+1)

Time and Space Complexity

• Time: O(n) because we will have to go till n/2 values at most.
• Space: O(n) because we will have to go till n/2 depth at most.