Check If The String Is A Palindrome

Posted: 31 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a string 'S'. Your task is to check whether the string is palindrome or not. For checking palindrome, consider alphabets and numbers only and ignore the symbols and whitespaces.

Note :

String 'S' is NOT case sensitive.

Example :

Let S = “c1 O$d@eeD o1c”.
If we ignore the special characters, whitespaces and convert all uppercase letters to lowercase, we get S = “c1odeedo1c”, which is a palindrome. Hence, the given string is also a palindrome.
Input format :
The very first line of input contains an integer 'T' denoting the number of test cases. 

The first line of every test case contains the string 'S'.
Output format :
For each test case, print “Yes” if 'S' is a palindrome, and “No” otherwise.

Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up :
Can you solve the problem using O(1) space complexity?
Constraints :
1 <= T <= 100 
1 <= Length(S) <= 10^4

Where 'T' denotes the number of test cases and 'S' denotes the given string.

Time Limit : 1 sec
Approach 1
  • A palindrome string is a sequence of characters which reads the same backward as forward. We use this property of palindrome to check whether the given string is a palindrome or not.
  • First off, we convert the given string to lowercase, this would make it easier for us to check for palindrome.
  • Now, the idea is to reverse the given string and store it in another variable.
  • We need to compare the original string with the reversed one.
  • During the comparison, we ignore the special characters, whitespaces and case of the string and consider only the alphabets and numbers.
  • We keep two pointers i and j, pointing to start of the given string and the reversed string respectively.
  • During each iteration, if both the pointer point to valid characters (i.e. alphabets or numbers only), we check if both the characters are equal or not.
    • If both characters are equal, we increment ith pointer and the jth pointer.
    • Otherwise, the string is not a palindrome.
  • Otherwise, if a pointer doesn’t point to a valid character (symbols and whitespaces are not valid), we skip that character and move the pointer to the next index.
  • We stop the iteration when the pointers reach the end of the string.
  • In this way, we can check if the given string is a palindrome or not.
Try Problem