Valid Palindrome
Program to check Valid Palindrome – Medium Level
Given a string s, return true if it is a palindrome, otherwise return false.
A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Output: true
Explanation: After considering only alphanumerical characters we have “wasitacaroracatisaw”, which is a palindrome.
Output: false
Explanation: “tabacat” is not a palindrome.
Constraints:
- 1 <= s.length <= 1000
- s is made up of only printable ASCII characters.
Valid Palindrome Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n) time and O(1) space, where n is the length of the input string.
Hints for solving problems
Hint 1 :
A brute force solution would be to create a copy of the string, reverse it, and then check for equality. This would be an O(n) solution with extra space. Can you think of a way to do this without O(n) space?
Hint 2 :
Can you find the logic by observing the definition of palindrome or from the brute force solution?
Hint 3 :
A palindrome string is a string that is read the same from the start as well as from the end. This means the character at the start should match the character at the end at the same index. We can use the two pointer algorithm to do this efficiently.
There are mainly 2 approach to solve this problem-
- Reverse String Method
- Two Pointer Method
1. Reverse String Method
This approach involves reversing the string representation of the array elements, sorting the reversed strings, and then checking for the longest consecutive sequence. However, it’s not commonly used for this problem as it focuses on string manipulation.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
bool isPalindrome(string s) {
string newStr = "";
for (char c : s) {
if (isalnum(c)) {
newStr += tolower(c);
}
}
return newStr == string(newStr.rbegin(), newStr.rend());
}
};
public class Solution {
public boolean isPalindrome(String s) {
StringBuilder newStr = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
newStr.append(Character.toLowerCase(c));
}
}
return newStr.toString().equals(newStr.reverse().toString());
}
}
class Solution:
def isPalindrome(self, s: str) -> bool:
newStr = ''
for c in s:
if c.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]
class Solution {
/**
* Check if a character is alphanumeric
* @param {char} char
* @return {boolean}
*/
isAlphanumeric(char) {
return (char >= 'a' && char <= 'z') ||
(char >= 'A' && char <= 'Z') ||
(char >= '0' && char <= '9');
}
/**
* @param {string} s
* @return {boolean}
*/
isPalindrome(s) {
let newStr = '';
for (let c of s) {
if (this.isAlphanumeric(c)) {
newStr += c.toLowerCase();
}
}
return newStr === newStr.split('').reverse().join('');
}
}
2. Two Pointers Method
In this method, you sort the array and use two pointers to iterate through the array while maintaining a count of consecutive elements to find the longest sequence. This is efficient when combined with sorting.
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !alphaNum(s[l])) {
l++;
}
while (r > l && !alphaNum(s[r])) {
r--;
}
if (tolower(s[l]) != tolower(s[r])) {
return false;
}
l++; r--;
}
return true;
}
bool alphaNum(char c) {
return (c >= 'A' && c <= 'Z' ||
c >= 'a' && c <= 'z' ||
c >= '0' && c <= '9');
}
};
public class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !alphaNum(s.charAt(l))) {
l++;
}
while (r > l && !alphaNum(s.charAt(r))) {
r--;
}
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
return false;
}
l++; r--;
}
return true;
}
public boolean alphaNum(char c) {
return (c >= 'A' && c <= 'Z' ||
c >= 'a' && c <= 'z' ||
c >= '0' && c <= '9');
}
}
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not self.alphaNum(s[l]):
l += 1
while r > l and not self.alphaNum(s[r]):
r -= 1
if s[l].lower() != s[r].lower():
return False
l, r = l + 1, r - 1
return True
def alphaNum(self, c):
return (ord('A') <= ord(c) <= ord('Z') or
ord('a') <= ord(c) <= ord('z') or
ord('0') <= ord(c) <= ord('9'))
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
isPalindrome(s) {
let l = 0, r = s.length - 1;
while (l < r) {
while (l < r && !this.alphaNum(s[l])) {
l++;
}
while (r > l && !this.alphaNum(s[r])) {
r--;
}
if (s[l].toLowerCase() !== s[r].toLowerCase()) {
return false;
}
l++; r--;
}
return true;
}
/**
* @param {char} c
* @return {boolean}
*/
alphaNum(c) {
return (c >= 'A' && c <= 'Z' ||
c >= 'a' && c <= 'z' ||
c >= '0' && c <= '9');
}
}
