Code Pumpkin

Program to check if given string is palindrome or not

August 29, 2018
Posted by Suyash Purwar

Introduction

In this series, I will publish lots of puzzles in JavaScript. I will provide multiple solutions for a program so that you can have a better understanding of the problem and solution. These types of questions are many times asked in interviews, so a good understanding of these type of puzzles might benefit you. I must say, this series definitely worth your time. If you are preparing for competitive programming, then you have landed in a right place because I will persistently make more and more articles regarding algorithms and puzzles in JavaScript. I am very excited. So, let's get started…

Note: I will follow the shortest syntax in solving these problems, you should be familiar with the ES6 syntax.

Puzzle

Write a program to check whether a string is a palindrome or not. A palindrome is a word which is the same when reading from the starting and ending. Like – 'madam', 'radar', 'lol' etc.

Solutions

First of all, Try to solve this problem on your own. To help you out I am here but first, try to solve this on your own. Always remember – You can only learn to code by doing it.

There can be many solutions for this program. Let's have a look on solutions which I found.

Solution 1:


function variantOne(word) {
	let isPalindrome = true;
	for (let a = 0, b=word.length-1; a <= b; a++, b--) {
		if (word[a] !== word[b]) {
			isPalindrome = false
		}
	}
	
	return isPalindrome ? "It's a palindrome" : "It's not a palindrome";
}

console.log(variantOne("code")); //   Output: "It's not a palindrome"
console.log(variantOne("WOW")); //   Output: "It's a palindrome"
console.log(variantOne("ABBA"); //   Output: "It's a palindrome"

This might seem complicated but it's not, this is the most efficient solution of it. In this solution, for-loop checks  the first character of word to the  last one. If both of them are equal, we will compare second and second-last characters. 

If we will keep getting same character, we will keep iterating till the middle of the loop. We don't require to iterate through entire loop.  isPalindrome flag remains true in this case.  We will break the loop, if we don't find the match and set isPalindrome to false

Time Complexity : If is a number of characters in a given string, then this approach will take n/2 iterations and hence time complexity is O(n).

Space Complexity : No extra space is required for this approach i.e. O(1)

This is easy, isn't it? Feel free to drop any question in a comment section below.

Now lets have a look at other solutions. Solution 2 to 6 uses the same principle i.e. If a given string and its reverse string are same, then given string is a palindromic string. However, time and space complexity is little bit more for these approaches. But it will help you practice and learn Javascript programming using ES6 syntax.

Solution 2: 


function variantTwo(word) {
   const reversed = word.split('').reverse().join('');     // (a)
   return word === reversed ? `It's a palindrome` : `It's not a palindrome`;   // (b)
}

console.log(variantTwo("madam")); //  Output: "It's a palindrome"
console.log(variantTwo("codepumpkin")); // Output: "It's not a palindrome"

In line (a), split('') method turns a string into an array, like this:


// split('') function splits the every character of string and transforms it into a array of characters

console.log("Pumpkin".split('')); //  Output: ['P', 'u', 'm', 'p', 'k', 'i', 'n'];

// This splitted array is then passed to reverse() function and then join('') function

After getting the array from split('') method, reverse() method runs, which reverses the array and then join('') method joins it. For instance:


console.log(['P', 'u', 'm', 'p', 'k', 'i', 'n'].reverse()); // Output: ['n', 'i', 'k', 'p', 'm', 'u', 'P']
console.log(['n', 'i', 'k', 'p', 'u', 'm', 'P'].join('')); // Output: "nikpmuP"

// This is how the string gets reversed

After getting reversed string in reversed variable that is declared at line (a), at line (b) comparison between the actual string and reversed string is taking place to make a decision whether the string is a palindrome or not.

Hope you understood, If you have any doubts don't hesitate to write it down in the comment section below.

Now, let's move on to other variants.

Solution 3:


function variantThree (word) {
   let reversed = ``;
   for (let i = 0; i < word.length; i++) {
      reversed = word[i] + reversed;
   }

   return word === reversed ? `It's a palindrome` : `It's not a palindrome`; // (a)
}

console.log(variantThree("radar")); //  Output: "It's a palindrome"
console.log(variantThree("car")); //  Output: "It's not a palindrome"

This variant doesn't use any built-in method, just a for-loop. It's easy, isn't it?

for-loop reverses the string and stores the reversed string in reversed variable. At line (a), the comparison is taking place between the actual string and reversed string to check whether a string is a palindrome or not. This is how this variant works.

Let's move forward to the fourth variant.

Solution 4:


function variantFour (word) {
   let reversed = ``;
   word.split('').forEach(char => {
      reversed += char;
   });

   return word === reversed ? `It's a palindrome` : `It's not a palindrome`;
}

Instead of using for-loop, this variant relies on forEach() method for looping over an array (which gets returned from split('') method). Always remember, forEach() method works on an array, this is the reason for using split('') method.

Rest of the code is similar to the solutions that are mentioned above and so there's functionality.

Solution 5:


function variantFive (word) {
   let reversed = ``;
   for (let char of word) {
      reversed = char + reversed;
   }

   return word === reversed ? `It's a palindrome` : `It's not a palindrome`;
}

In this method, instead of looping over an array, we are looping over a string. This solution is relying on for...of loop for looping over a string. for...of loop is extracting the reversed string from the actual string and storing it in a variable.

I know that you are smart enough to guess next steps. wink

Solution 6:


function variantSix (word) {
   return word.split('').reduce((reversed, word) => reversed = word + reversed, '') === word ? `It's a palindrome` : `It's not a palindrome`;
}

WHOAA!!!. You might be quite amazed to see that we are not using any kind of for-loop. This variant uses reduce() method, which also works over an array.

This variant might seem complicated to you but believe me, it's not. Start practicing programming in ES6 syntax, and you will start loving this new way of functional programming.

Now let's analyze time and space complexity of above five solutions (Solution 2 to Solution 6).

Time Complexity : If is a total number of characters in a given string, then we will require to iterate through all the characters in order to reverse the string. So total operations are required, so time complexity is still O(n). However Solution one was providing better time complexity.

Space Complexity : We are storing reversed string in extra string variable, so we will require O(n) more space. In Solution 1, do not require this extra space as well. 

These are all the solutions that I found. If you find any new variant, please mention it in a comment section. And wait,  Do share and comment, if you think that this article worths reading. 

That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.

Happy Learning 🙂



About the Author


A tech guy who loves to code and design edge-cutting websites and mobile apps. I'm open source enthusiast and a delicious coffee maker



Tags: ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.
Total Posts : 112
follow us in feedly
Contribute Your Articles

Subscribe Us

Like Us On Facebook