RUN


A palindrome is a string which on reversal, is same as the string initially. In the above example of reversing a string, we see two strings:

  1. FACE
  2. MADAM

On reversing the strings, we get FACE as ECAF while MADAM stays unaffected by reversal. Thus, MADAM is a palindrome.


Similarly, we have different strings like RADAR, ANNA and LEVEL. We can also have multiple WORD palindromes like

  • My gym
  • Red rum, sir, is murder
  • Step on no pets

So, how to solve this problem. Firstly, keep your IDE closed, and pick up a copy and a pen to write down the pseudo-code. For solving this problem, we have two approaches

 

# APPROACH 1: Brute Force

Yes, Let’s get down to brass tacks. Simply put, this will have three steps.

Pseudo Code:

  1. Store the string // input
  2. Iterate over the string backwards // for loops
  3. Check if the strings are equal

This is the easiest solution possible. We are calculating the entire possibility of reversal of string and then comparing it. The code will go like this:

Code:

#include <iostream>
include < string.h >
using namespace std;

int main() {

   char string1[20], stringReversed[20];

   int i, length, j;

   int flag = 0;

   cout << "Enter a string: ";
   cin >> string1;

   length = strlen(string1);

   for (i = length - 1, j = 00. >= 0, j < length; i--, j++) {

      stringReversed[j] = string1;

   }

   for (i = 0; i < length; i++) {

      if (string1[i] != stringReversed[i])

      {

         flag = 1;

         break;

      }

   }

   if (flag) {

      cout << string1 << " is not a palindrome-“ « endl;

   } else {

      cout << string1 << " is a palindrome- “« endl;

   }

   return 0;

}

We first reverse the string by using two variables, I which starts from the front and j which starts from the back. This reversal is then completed, after which we evaluate if the strings are equal or not.

The run time of this solution is O(n) and this increases as the size of the string increases.

 

# APPROACH 2: Optimized Solution

In the above approach, what if instead of iterating the whole string and then using another loop to compare, we only iterate half a string and compare in the same loop? Since we know that the first half will be equal to second half in a palindrome, we use this as the improvement while devising our second algorithm.

 

Pseudo Code:

  1. Iterate over the string once, with one variable at the front and other variable at the back.
  2. Check and compare the variables at each iteration
  3. If all iterations are passed, we have a palindrome.

Code:

The run time of this solution is O(n/2) . And as clearly visible, we use a lot less looping.

#include <iostream>
#include <string.h>
using namespace std., '

int main() {

      char string1[20];

      int i, length;

      int flag = 0;

      cout << "Enter a string:"; 
      cin >> string1;

      length = strlen(string1);

      for (i = 0; i < length; i++) {

         if (string1[i] != string 1[length - i - 1] {

               flag = 1;

               break;

            }

            if (flag) {

               cout << stringl<< " is not a palindrome" << endl;

               else {

                  cout << string 1 << " is a palindrome";

                  return 0;

               }

This is how we solve the check palindrome problem.

 

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020