Back to DSA
Valid Palindrome
easyDetermine whether a given string qualifies as a palindrome after preprocessing. Preprocessing involves converting every letter to lowercase and discarding all characters that are not letters or digits. A palindrome reads identically from both ends.
Examples
Example 1:
Input:
s = "Was it a car or a cat I saw"Output:
trueExplanation: After stripping non-alphanumeric characters and lowering case, the result is 'wasitacaroracatisaw', which is a palindrome.
Example 2:
Input:
s = "hello world"Output:
falseExplanation: The cleaned string 'helloworld' does not read the same forwards and backwards.
Hints
class Solution {
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}Time complexity
O(n)Space complexity
O(1)