In this guide, you will get 125. Valid Palindrome LeetCode Solution with the best time and space complexity. The solution to Valid Palindrome problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Constraints:
1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
125. Valid Palindrome LeetCode Solution in C++
class Solution {
public:
bool isPalindrome(string s) {
int l = 0;
int r = s.length() - 1;
while (l < r) {
while (l < r && !isalnum(s[l]))
++l;
while (l < r && !isalnum(s[r]))
--r;
if (tolower(s[l]) != tolower(s[r]))
return false;
++l;
--r;
}
return true;
}
};
/* code provided by PROGIEZ */
125. Valid Palindrome LeetCode Solution in Java
class Solution {
public boolean isPalindrome(String s) {
int l = 0;
int r = s.length() - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l)))
++l;
while (l < r && !Character.isLetterOrDigit(s.charAt(r)))
--r;
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
return false;
++l;
--r;
}
return true;
}
}
// code provided by PROGIEZ
125. Valid Palindrome LeetCode Solution in Python
class Solution:
def isPalindrome(self, s: str) -> bool:
l = 0
r = len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True
# code by PROGIEZ
