Last Updated on May 15, 2023 by Prepbytes
When we say something is a palindrome, we mean that even when it is reversed, it retains its original shape. For instance, the word "naman" is a palindrome since it remains the same when reversed.
When an object is reversed and the result is the same as the original, it is said to be a palindrome. An object can be anything, including a number, string, word, or anything else. Palindrome numbers are those whose values are unaffected by the reversal of their digits. For instance, the number 491194 is a palindrome because, when reversed, its digits remain the same. A string is said to be a palindrome if its reverse is the same as the original string. One example is that "ABBA" is a palindrome while "ANKIT" is not.
Algorithm for Palindrome in C
The following logic can be used to determine whether or not the provided object is a palindrome:
Algorithm 1
- Obtain the input object that will be tested to see if it is a palindrome.
- Next, compute the input object’s opposite and store the result in a different variable.
- Now determine if the original input object obtained and the reverse calculation are equivalent or not, and then save the outcome in the bool variable.
- The supplied object is a palindrome if the calculated bool value has the value true; otherwise, it is not a palindrome.
Time Complexity: O(n) Because the entire string must be traversed in this case, the time complexity is O(n).
Space Complexity: O(n) The space complexity in this case is O(n) because we require an additional space of the same size as the array in order to reverse the string and store it.
Algorithm 2
- Obtain the input object that will be tested to see if it is a palindrome.
- Take the start pointer and the end pointer now. The start pointer and the end pointer both point to the beginning and end of the input, respectively.
- Check the values at both pointers, and if they are equal, increment the start pointer and decrement the end pointer; if not, break since the input is not a palindrome.
- Repetition of step 3 is required until the start and end pointers are at the same place or until the start pointer reaches location (n/2), where n is the input’s length.
Time Complexity: O(n) Because the entire string must be traversed in this case, the time complexity is O(n).
Space Complexity: O(1) Since we require additional space in this situation, the space complexity is O(1).
Example Program for Palindrome in C
Now, we would create computer programs employing various methods to determine whether or not the supplied object is a palindrome.
Using While Loop in C
Here, we will discuss 2 different algorithms for C program to check if a given string is palindrome or not.
Algorithm 1
In this case, we would run over the string and reverse it using a while loop. After flipping the string, we would compare the two strings to determine whether or not it was a palindrome. After reversing, we would compare the string to the original string using the strcmp() function, which returns 0 if both strings are identical. If the string is identical to the reversed one, then it would return 0 which would mean that the given string is a palindrome. For reversing, we would traverse the entire string and store its reverse in a new string rev using a while loop.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
int main() {
// str is the string to be cheked for palindrome
char str[] = "cabbac";
int l = sizeof(str);
char rev[l + 1];
int i = l - 2;
// while loop to reverse the string
while (i >= 0) {
rev[l - i - 2] = str[i];
i--;
}
// compare the initial string and reversed string
int res = 0;
if (res == 0) {
printf("%s is a Palindrome\n", str);
} else {
printf("%s is not a Palindrome\n", str);
}
}
Output
cabbac is a PalindromeNote: As indexing is zero based, the last character should be at position l-1 for length l, but since this is a character array, it has an additional end line character (‘null’) as the last character; therefore, for the last character of the string, we would be using l-2.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(N), where ‘N’ denotes the string’s length.
Algorithm 2
In this case, a while loop would be used to run over the string and compare the values at the start and end pointers to determine whether or not it is a palindrome. By using a while loop to compare the start and end pointers and each character individually, we can determine whether the provided string is a palindrome or not.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
int main() {
// str is the string to be cheked for palindrome
char str[] = "naman";
int l = sizeof(str);
int start = 0, end = l - 2;
// here end is equal to l-2 as in case of character array
//there is always Null pointer at the end therefore
//we take end poniter as l-2
int ispalin = 1;
// while loop to compare values of both start and end values of the string
while (start <= end) {
if (str[start] != str[end]) {
printf("%s is not a Palindrome\n", str);
ispalin = 0;
break;
}
start++;
end--;
}
if (ispalin) {
printf("%s is a Palindrome\n", str);
}
}
Output
naman is a PalindromeAs we can see in the example above, the string naman is a palindrome because each time we iterate it, the start and end pointers have the same value.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(1), Since there is no extra space being used.
Using Do-while Loop in C
Here, we will discuss 2 different algorithms for C program to check if a given string is palindrome or not.
Algorithm 1
Here, we would reverse the string iteratively using a do-while loop. After flipping the string, we would compare the two strings to determine whether or not it was a palindrome. After reversing, we would compare the string to the original string using the strcmp() function, which returns 0 if both strings are identical. If the string is identical to the reversed one, then it would return 0 which would indicate that the given string is a palindrome. For reversing, we would traverse the entire string and store its reverse in a new string rev using a do-while loop.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
// str is the string to be checked for palindrome
char str[] = "PrepBytes";
int l = sizeof(str);
char rev[l + 1];
int i = l - 2;
// do while loop to reverse the string
do {
rev[l - i - 2] = str[i];
i--;
} while (i >= 0);
// compare the initial string and reversed string
int res = strcmp(str, rev);
if (res == 0) {
printf("%s is a Palindrome\n", str);
} else {
printf("%s is not a Palindrome\n", str);
}
}
Output:
PrepBytes is not a PalindromeTime Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(N), where ‘N’ denotes the string’s length.
The string is a palindrome because, as we can see, the reversed form of cabbac is the same as cabbac.
Algorithm 2
In this case, a do-while loop would be used to iterate over the string and compare the values at the start and end pointers to determine whether or not it is a palindrome. By utilizing a do-while loop to compare the start and end pointers and compare each character individually, we can determine whether the provided string is a palindrome or not.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
// str is the string to be cheked for palindrome
char str[] = "naman";
int l = sizeof(str);
int start = 0, end = l - 2;
// here end is equal to l-2
//as in case of character array is null therefore we take it as l-2
int ispalin = 1;
// do while loop to compare values of both start and end values of the string
do {
if (str[start] != str[end]) {
printf("%s is not a Palindrome\n", str);
ispalin = 0;
break;
}
start++;
end--;
} while (start <= end);
if (ispalin) {
printf("%s is a Palindrome\n", str);
}
}
Output:
naman is a PalindromeAs we can see in the example above, the string naman is a palindrome because each time we iterate it, the start and end pointers have the same value.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(1), Since there is no extra space being used.
Using For Loop in C
Here, we will discuss 2 different algorithms for C program to check if a given string is palindrome or not.
Algorithm 1
Here, the string would be iterated over and reversed using a for loop. After flipping the string, we would compare the two strings to determine whether or not it was a palindrome. Using a for loop, we would traverse the entire string to reverse it, then store the reverse in a new string called rev. After the string had been reversed, we would compare it to the original string using the strcmp() function, which returns 0 if the two strings are identical. If the original string and the reversed string are identical, then the function would return 0 and the given string would be a palindrome.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
// str is the string to be cheked for palindrome
char str[] = "PrepBytesTopics";
int l = sizeof(str);
char rev[l + 1];
int i = l - 2;
// for loop to reverse the string
for (int i = l - 1; i >= 0; i--) {
rev[l - i - 2] = str[i];
}
// compare the initial string and reversed string
int res = strcmp(str, rev);
if (res == 0) {
printf("%s is a Palindrome\n", str);
} else {
printf("%s is not a Palindrome\n", str);
}
}
Output:
PrepBytesTopics is not a PalindromeAs we can see that the reversed string of PrepBytesTopics is not the same as scipoTsetyBperP, Therefore, the string is not a palindrome.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(N), where ‘N’ denotes the string’s length.
Algorithm 2
Here, the start and end pointers of the string will be iterated over and their values compared to determine whether the string is a palindrome or not. By using a for loop to compare the start and end pointers and compare each character individually, we can determine whether the supplied string is a palindrome or not.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
// str is the string to be cheked for palindrome
char str[] = "naman";
int l = sizeof(str);
int end = l - 2;
// here end is equal to l-2
//as in case of character array is null therefore we take it as l-2
int ispalin = 1;
// for loop to compare values of both start and end values of the string
for (int start = 0; start <= end;) {
if (str[start] != str[end]) {
printf("%s is not a Palindrome\n", str);
ispalin = 0;
break;
}
start++;
end--;
}
if (ispalin) {
printf("%s is a Palindrome\n", str);
}
}
Output
naman is a PalindromeAs we can see in the example above, the string naman is a palindrome because each time we iterate it, the start and end pointers have the same value.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(1), Since there is no extra space being used.
Using Recursion in C
Here, we will discuss 2 different algorithms for C program to check if a given string is palindrome or not.
Algorithm 1
Recursion would be used in this case to iterate over the string and flip it. After flipping the string, we would compare the two strings to determine whether or not it was a palindrome. Recursion was used to reverse the string, and the base condition for the string is when the start pointer exceeds the end pointer. To reverse the string, we swapped the first and last character. After reversing, we would compare the string to the original string using the strcmp() function, which returns 0 if both strings are identical. If the string is identical to the reversed one, then it would return 0 which would indicate that the given string is a palindrome. For reversing, we would traverse the entire string and store its reverse in a new string rev using recursion.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void reverse(char *x, int st, int end) {
char t;
if (st >= end)
return;
t = *(x + st);
*(x + st) = *(x + end);
*(x + end) = t;
reverse(x, ++st, --end);
}
int main() {
// str is the string to be cheked for palindrome
char str[] = "cabbac";
char rev[] = "cabbac";
int l = sizeof(str);
// recursion to reverse the string
reverse(rev, 0, l - 2);
// compare the initial string and reversed string
int res = strcmp(str, rev);
if (res == 0) {
printf("%s is a Palindrome\n", str);
} else {
printf("%s is not a Palindrome\n", str);
}
}
Output
cabbac is a PalindromeSince the reversed string of cabbac is identical to cabbac, hence, the string is a palindrome.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(N), where ‘N’ denotes the string’s length.
Algorithm 2
Here, we would go over the string using recursion to compare the values at the start and end pointers and determine whether or not it is a palindrome. Recursion is used to compare the values at the start and end pointers in this case, and it is then called on more strings until the start pointer is smaller than the end pointer.By using recursion to compare the start and end pointers and each letter individually, we can determine whether the provided string is a palindrome or not by checking whether any of the pointers match.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int ispalindrome(char *x, int st, int end) {
if (st >= end)
return 0;
if (x[st] == x[end]) {
int res = ispalindrome(x, st + 1, end - 1);
return res;
}
return -1;
}
int main() {
// str is the string to be cheked for palindrome
char str[] = "racecar";
int l = sizeof(str);
// recursion to compare values of both start and end values of the string
int res = ispalindrome(str, 0, l - 2);
if (res != (-1)) {
printf("%s is a Palindrome\n", str);
} else {
printf("%s is not a Palindrome\n", str);
}
}
Output:
racecar is a PalindromeAs we can see in the example above, the string "racecar" is not a palindrome since each time we iterate it, the start and end pointers don’t have the same value.
Time Complexity: O(N), where ‘N’ denotes the string’s length.
Space Complexity: O(N), The recursive call stack would be constructed up to the length of the string even if we are not utilizing any additional space, making the space complexity O(N).
Conclusion
If an object reads the same from beginning to end, it is said to be a palindrome. These steps can be used to determine whether or not an object is a palindrome:
- One option in C is to reverse the string and compare each character individually.
- Another method is to compare the first and last character in a string one at a time until we either reach the center of the string or find a character that differs between the first and last pointer.
FAQ Related to C Program to Check if a Given String is Palindrome or Not
Q1. Can we check if numbers are palindrome or not?
Ans. The answer is YES, we can check if the number present is palindrome or not, by simply checking if the values are the same for the first digit with the last one, then second digit with the second last one and more.
Q2. Is the C program to check if a given string is palindrome or not is an important program?
Ans. Yes, It is generally asked in many service based companies like TCS, Wipro, Accenture, Cognizant etc in their interview rounds.
Q3. How do you tell whether or not a string is a palindrome?
Ans. If a string’s reverse is the same as the original, it is referred to as a palindrome string. For instance, level, radar, etc.