Check If The String Is A Palindrome
Last Updated: 31 Dec, 2020
Difficulty: Easy
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.
Approach 2
- 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 whole string to lowercase, this would make it easier for us to check for palindrome.
- Now, the idea is to simultaneously iterate over the start and end of the string and check if the string is a palindrome.
- During the iteration, 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 and end of the string respectively.
- The ith pointer traverses the string from the start, whereas the jth pointer traverses the string from the end.
- 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 the ith pointer and decrement 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 both the pointers become equal, i.e. i=j.
- In this way, we can check if the given string is palindrome or not.
SIMILAR PROBLEMS
Divisible Substrings
Posted: 29 Jul, 2022
Difficulty: Easy
Ninja and Numbers
Posted: 30 Jul, 2022
Difficulty: Moderate
Longest Palindromic Substring
Posted: 4 Sep, 2022
Difficulty: Moderate
Cakes
Posted: 23 Sep, 2022
Difficulty: Easy
1-3 Palindrome
Posted: 4 Oct, 2022
Difficulty: Easy
