Program to Check Palindrome String in C, Python

Program to Check Palindrome String in C, Python

In this program, we check how to write the code to identify if the given string is palindrome or not. Before writing a program for palindrome you should know what is palindrome string.

What is Palindrome String?

The string is called a palindrome string if it is read the same forward and backward. In other words, if we reverse the string, it should be identical to the original string.

Palindrome String Example:

String “madam” and “radar” are palindrome strings.

Algorithm to Check Palindrome String

Consider you have given a string.

Algorithm:

Step 1: 
Set the two pointers: 
 - pointer pointing to first (forward Pointer) and 
 - pointer pointing to last character (backword pointer).

Step2: 
 Match the characters pointed by both pointers.

Step 3: 
 If matches, move forward pointer by one to right and move the backward pointer by one to left. And repeat the step 2.
 If don't match, print output as "String is not palindrome"

Difficulty level: low

C Program for Palindrome

We can do this programmatically in the easiest way. Use the string function strrev() provided in string.h library. It reverses the given string. By matching an original string with a reversed string, we can find out if the string is palindrome or not.

Here is a simple C program for palindrome.

#include <stdio.h>
#include <string.h>
  
int main()
{
   char sString[100] = {0};
  
   printf("Enter the string to check if it is a palindrome\n");
   gets(sString);
 
   if (strcmp(sString, strrev((char*)sString)) == 0)
      printf("Given String is a palindrome.\n");
   else
      printf("Given String is not a palindrome.\n");
  
   return 0;
}

Output:

Case 1:

Enter the string to check if it is a palindrome
"radar"
Given String is a palindrome.

Case 2:

Enter the string to check if it is a palindrome
"csestack"
Given String is not a palindrome.

Note:

On some systems, you may come across an error as “Undefined reference to strrev“. This is all because strrev() is not supports in the C-GCC compiler. It is present in ANSI C (Turbo C/C++) compilers.

In the case of the C-GCC compiler, you have to write code to reverse the string manually and then have to match the string.

Python Program for Palindrome

Here is simple program in Python to check if the given string is palindrome or not.

str_msg = "radar"

if str_msg == str_msg[::-1]:
  print(f"{str_msg} is a palindrome string.")
else:
  print(f"{str_msg} is not a palindrome string.")

Output:

radar is a palindrome string.

Here, we are using extended slice syntax for reversing the string.

You can try executing the above Python code for different string.

Complexity

Considering the number of characters in the string as n, reversing and comparing would take O(n) time each. This leads to the total complexity of O(n).

[Complexity of the program has updated as per the correction by Amey in the comment. Thanks, Amey!]

6 Comments

  1. “It takes constant times to execute for any string. So it has the complexity of O(1)”

    I do not agree with this. Considering no. of characters in the string as n, reversing and comparing would take O(n) time each. which would lead total complexity to be O(n).

    The given approach add a constant of 2 to overall complexity. Instead I suggest following

    1. set leftPtr to left end of string and rightPtr to right end of string
    2. compare characters at leftPtr with rightPtr, if they are not equal, goto 5 else continue
    3. increment leftPtr and decrement rightPtr
    4. if leftPtr > rightPtr goto 5 else goto 1
    5. end

    1. Thanks Amey to point it out. Actually, It is the good thread to discuss over.

      I can not deny your answer and it is absolutely correct. But the thing that I have considered here as – we are using system function to reverse the string and to match the string. As it is system call (both reversing the string and comparing it) we are not bothering to its impact on the complexity of the program.

      And if we consider the complexity of system functions, of course, your suggested solution is always preferable. it is the same algorithm mentioned in this article.

      1. Even if we assume that we use system string function, still it has some cost associated with it and hence the complexity will never be constant…irrespective of whether system function is used or not (This assuming that base for complexity, i.e., n is number of characters.)

  2. This is a normal recursive program which works perfectly, why we need to solve it like Matrix Chain Multiplication problem ?

Leave a Reply

Your email address will not be published. Required fields are marked *