Leetcode in Rust: #125 - Valid Palindrome
Written by Katrina Ellison Geltman on Mon 06 October 2025.
https://leetcode.com/problems/valid-palindrome
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.
Solution #1 - Readable, but Suboptimal
This solution runs quickly, but allocates a new Vec<char> to hold the
alphanumeric characters.
// Runtime of 0 ms beats 100%
// Memory of 2.73 MB beats 12.84%
pub fn is_palindrome(s: String) -> bool {
let t: Vec<char> = s
.to_lowercase()
.chars()
.filter(|x| x.is_alphanumeric())
.collect();
if t.is_empty() {
return true;
}
let mut i = 0;
let mut j = t.len() - 1;
while i < j {
if t[i] != t[j] {
return false;
}
i += 1;
j -= 1;
}
}
Solution #2 - Optimal
This solution is more memory efficient than #1. It iterates directly over the input string, skipping non-alphanumeric characters.
// Runtime of 0 ms beets 100%
// Memory of 2.30 MB beats 93.51%
pub fn is_palindrome(s: String) -> bool {
let mut i = 0;
let mut j = s.len() - 1;
while i < j {
// Note: as_bytes() is OK because problem statement says s only contains ASCII
while !s.as_bytes()[i].is_ascii_alphanumeric() && i < s.len() - 1 {
i += 1;
}
while !s.as_bytes()[j].is_ascii_alphanumeric() && j > 0 {
j -= 1;
}
if i >= j {
return true;
}
if s.as_bytes()[i].to_ascii_lowercase() != s.as_bytes()[j].to_ascii_lowercase() {
return false;
}
if i < s.len() - 1 {
i += 1;
}
if j > 0 {
j -= 1
};
}
true
}