What is a Palindrome?

A palindrome is a special type of word that can be spelled the same backward and forward.

Examples of Palindromes: mom, dad, eye, ewe, noon, poop, peep, etc.

Palindromes can be words, sentences, groups of numbers, or even equations

Examples of longer palindromes: racecar, madam, kayak, redder, etc.

Sentences can also be written as palindromes. When you write a sentence a palindrome, you can re-arrange punctuation and capital letters.

• Madam, I’m Adam.
• I did, did I?
• He did, eh?
• Never odd or even.
• Nurses run!
• Oh no, Don ho!
• Step on no pets!
• Too hot to hoot

Some numbers can also be palindromes. Maybe you were even born in a palindromic year!

• 2002
• 1991
• 1771
• 100,001
• 111,111,111 x 111,111,111 = 12,345,678,987,654,321

Now you understand what palindrome is. First, let’s write some code to determine if a word is a palindrome.

Iterative solution

Explanation: The solution compares every character in the first half to the second half of the word. If the characters are not a mirror of each other, we will return false. If we successfully compare the whole half of the word, we can confirm that the word is a palindrome.

Space Complexity: 2 new variables with constant values so O(1)

Time complexity: Loop through half of the word so O(n/2) or O(n).

Recursive solution

Explanation: This solution is very similar to the iterative one. Since it is a recursive solution, we need a base case where we can stop the recursive loop. In our case, if the start and end characters are equal, we return true and continue to move inward to the next start and end characters. If the characters are not the same, we return false. Otherwise, when we exhaust all characters, we return true.

Space Complexity: Half the length of the word time recursive calls so O(n/2) or O(n).

Time Complexity: Similar to iterative O(n/2) or O(n)

Now let’s modified the solution to check if a sentence is a palindrome. In order for a sentence to be palindromic, we need to remove all the punctuations and special characters and spaces. We can employ the power of regex!!!

Wow! That’s powerful. replace(/[^\w]/gi, "") will replace all the special characters and spaces with an empty string for us.

Let’s see if we can write a function that will check if a number is a palindrome with converting it to a string. Otherwise, it is too easy! I think we can, right?!

Explanation: The solution is pretty straigh forward. We can apply the same principle as a string. However, we can find the length of a number. So we need a way to extract the leading and trailing digits from the number and modify the number after each iteration. Math is here to rescue us!

Space Complexity: We have 2 variables for leading and trailing half of the length of the number which is O(n/2 * 2) or O(n).

Time Complexity: Similarly we loop through half of the length of the number O(n/2) or O(n).

Thank you for reading! Let’s me know what you like me to cover next :D

Happy Coding!!!