Palindrome Checker

The Palindrome checker is an easy algorithm by most standards and a pretty popular one at that. The prompt usually goes :

Write a function that takes in a non-empty string and returns a boolean representing whether the string is a palindrome

NB: A palindrome is a word that spells the same thing forwards and backward. For example, if the sample input is 'aba' or 'dad', then these are palindromes and the output should be true.

Pretty easy right. Yeah, it is but I picked up a few important lessons and nuances about this problem during and after solving it.

Firstly, it important to take time to re-read the question, check for any 'detail' words which might be constraints/ helpers, and immediately clarify any ambiguity. For instance, in this problem, the prompt already states that the input is a 'non-empty string' which means no other data types are allowed. If this wasn't stated, it would be super important to cater for it before diving headfirst and failing all the test cases. Another possible point of ambiguity is how 'single lettered' strings should be handled. These questions prevent you from running into roadblocks later on and show thoughtfulness.

My Solutions

Solution 1

function isPalindrome(string) {
  // Write your code here.
    //single letter return true
    let stringLength = string.length
    if(stringLength == 1) return true
    return string == string.split('').reverse().join('')
}

The code is straight forward, it returns the comparison of the input string and the reversed string at once after catering for the single letter input. Time complexity O(n) and space complexity O(1) where n is the length of the input string. Easy Peasy. Just in case the interviewer says "Hey, you can't use inbuilt methods", I decided to come up with other solutions.

Solution 2

function isPalindrome(string) {
let reversedString= ""
if(string.length == 1) return true
for(let i= string.length-1; i >=0; i--){
reversedString +=  string[i] 
}
    return string == reversedString
}

The code is also similar but doesn't use any inbuilt methods. A 'reversedString' variable is declared initially. Then a for-loop starting from the end of the input string simply builds the reverse by adding to the variable declared outside the loop. The final result is a comparison of the sample input and the reversedString we just formed. Space Complexity now changes to O(n) which isn't as great as the previous solution and time complexity becomes O(n) or so I thought. The truth is the way javascript and a lot of other languages handle the string concatenation isn't the simple addition I thought. Strings are immutable primitives, so any addition to them means a new string is created and that basically causes a loop on the existing letters before the new letter is added. Yeah, it was weird initially but now I see why.

Solution 3

function isPalindrome(string) {
     let result = true 
    let leftPointer = 0
    let rightPointer = string.length - 1

    if(string.length == 1) return true    
    while(leftPointer < rightPointer){        
        if(string[leftPointer] != string[rightPointer]) result = false                
        leftPointer++
        rightPointer--
    }    
    return result
}

My third solution was to use a while loop. While loops help me to control the iteration and data manipulation within the loop. The goal was to establish two pointers and have them run from the two ends of the string. A palindrome would have the value of the two pointers always equal and the moment that condition isn't met, then it's time to return the false result. The space complexity is O(1) which is constant and the time complexity is O(n) which is linear time.

It wasn't a difficult problem altogether but still one I learned from and that's the goal. I hope you picked up something too. Till my next problem.

Ciao