Palindrome string

An algorithm to check if a given string is palindrome or not.

Strings are zero indexes based just like arrays in javascript, so we can use this to check if a string is a palindrome or not.

Example

Input:
'abba'
'learnersbucket'
'ABCDCBA'

Output:
true
false
true

We are going to use different methods to solve this.

• Using brute force method.
• Using String and Array methods of JavaScript.

Using brute force method

Implementation

• We are going to check if half of the string is matching to it’s other half.

//Function to check if a given string is palindrome
function checkPalindrome(str){
  var i, len = str.length;
  for(i = 0; i < len / 2; i++){
    if (str[i]!== str[len -1 -i])
       return false;
  }
  return true;
}

Input:
console.log(checkPalindrome('abba'));
console.log(checkPalindrome('learnersbucket'));
console.log(checkPalindrome('ABCDCBA'));

Output:
//How it works
/*
 strings are 0 index based just like arrays
 str = 'abba'
 len = str.length = 4;
 loop
  i = 0; i < 4 / 2; i++
   if(str[0](a) !== str[4-1-0](a))
      return false;

 i = 1; i < 4 / 2; i++
   if(str[1] (b) !== str[4-1-1] (b))
      return false;

i = 2 which is not less than 4 / 2 so break
finished
*/
true
false
true

Time complexity: O(N).
Space complexity: O(1).

Time and Space complexity

• We are checking the half of the string with it's other half i.e N/2, Time complexity is O(N).
• We are using constant space, Space complexity is O(1).

Using String and Array methods of JavaScript

Implementation

• We are going to split the string in an array of characters using String split() method.
• Then we are going to reverse the array and join again to create a string from it.
• Check if both matches.

//Function to check if a given string is palindrome
function checkPalindrome(str) {
    return str == str.split('').reverse().join('');
}

Input:
console.log(checkPalindrome('abba'));
console.log(checkPalindrome('learnersbucket'));
console.log(checkPalindrome('ABCDCBA'));

Output:
//Hot it works
/*
  str = 'abba'
  split the string in array of characters
  str.split('')  //splits and returns an array ['a','b','b','a']
  .reverse() //reverses an array ['a','b','b','a']
  .joins(''); //joins the array and returns a string  'abba'
*/
true
false
true

Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(n) where n is no of characters in the string.

Time and Space complexity

• We are first splitting the string which takes O(n) time where n is the length of the string, then we are reversing the array which also takes O(n) time and in the end we are joining the array which will take O(n) time. As these operations are being performed one after another i.e O(n) + O(n) + O(n), Time complexity is O(n).
• We are splitting the string and creating an array of characters, Space complexity is O(n) where n is the no of characters in a string.