LeetCode link: 125. Valid Palindrome, difficulty: Easy.
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 * 10^5sconsists only of printable ASCII characters.
Intuition
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
- Remove invalid characters.
- Use
valid_s == valid_s.reverseto check whether it is a palindrome.
Complexity
Time complexity
O(N)
Space complexity
O(1)
Ruby #
# @param {String} s
# @return {Boolean}
def is_palindrome(s)
valid_chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
valid_s = ''
s.downcase.chars.each do |char|
if valid_chars.include?(char)
valid_s << char
end
end
valid_s == valid_s.reverse
end
Python #
class Solution:
def isPalindrome(self, s: str) -> bool:
valid_chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
valid_s = ''
for char in s.lower():
if char in valid_chars:
valid_s += char
return valid_s == valid_s[::-1]
Java #
class Solution {
public boolean isPalindrome(String s) {
var validChars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
var validS = new StringBuilder();
for (char c : s.toLowerCase().toCharArray()) {
if (validChars.indexOf(c) != -1) {
validS.append(c);
}
}
var cleaned = validS.toString();
var reversed = validS.reverse().toString();
return cleaned.equals(reversed);
}
}
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 125. Valid Palindrome. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
- π Free Custom Domain: Bind your own personal domain for freeβforever.
- β¨ Premium Subdomains: Stand out with elite tech handle like
name.leader.me.