A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:
Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.
Example 3:
Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.
This program checks whether a given string s is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome reads the same backward as forward after processing. The solution first preprocesses the string to remove non-alphanumeric characters, convert uppercase letters to lowercase, and retain only valid characters (letters and numbers). Then, it compares the original processed string with its reverse to determine if it is a palindrome.
The program begins by calculating the size of the input string `s` using `s.size()`. It initializes an empty string `str` to store the processed characters. A `for` loop iterates through each character of `s`. Inside the loop, it checks if the character is an uppercase letter (ASCII value between 65 and 90). If true, it converts the character to lowercase by adding 32 to its ASCII value and appends it to `str`. If the character is a lowercase letter (ASCII value between 97 and 122) or a digit (ASCII value between 48 and 57), it is directly appended to `str`. This process ensures that `str` contains only lowercase alphanumeric characters.
After preprocessing, the program calculates the size of `str` and initializes another string `ans` to store the reverse of `str`. Using another `for` loop, it iterates through `str` in reverse order, appending each character to `ans`. Once `ans` is constructed, a third loop compares each character of `str` and `ans` at corresponding positions. If any mismatch is found, the program returns `false`, indicating that the string is not a palindrome. If no mismatches are found, it returns `true`.
For example, consider the input `s = "A man, a plan, a canal: Panama"`. After preprocessing, `str` becomes `"amanaplanacanalpanama"`. The reverse of this string is identical, so the function returns `true`. For the input `s = "race a car"`, the processed string is `"raceacar"`, and its reverse is `"racacear"`. Since they are not equal, the function returns `false`. In the case of `s = " "`, the processed string is an empty string `""`, which is considered a palindrome, so the function returns `true`.
This implementation works efficiently but can be optimized. Instead of creating the reverse string explicitly, we can use two pointers to compare characters directly from the start and end of the string. This reduces space complexity. The given approach has a time complexity of \(O(n)\), where \(n\) is the length of the string, as it involves traversing the string multiple times. The space complexity is \(O(n)\) due to the creation of the `str` and `ans` strings. Overall, the program handles edge cases, such as empty strings, strings with only non-alphanumeric characters, and mixed-case inputs, effectively ensuring correct results in all scenarios.
CODE:
class Solution {
public:
bool isPalindrome(string s) {
int n=s.size();
int i,j;
string str;
for(i=0;i<n;i++){
if(s[i]>=65&&s[i]<=90){
str+=s[i]+32;
}
else if(s[i]>=97&&s[i]<=122){
str+=s[i];
}
if(s[i]>='0'&&s[i]<='9'){
str+=s[i];
}
}
int m=str.size();
string ans;
for(i=0;i<m;i++){
ans+=str[m-1-i];
}
for(i=0;i<m;i++){
if(ans[i]!=str[i]){
return false;
}
}
return true;
}
};
0 Comments