Sponsored
Sponsored
This approach employs two pointers: one starting at the beginning of the string and the other at the end. The algorithm checks if the characters at these pointers are the same, ignoring case and non-alphanumeric characters. If they match, both pointers move inward. If they don't or if any pointer surpasses the other, the string is not a palindrome.
Time Complexity: O(n), where n is the length of the string, because we go through the string at most once.
Space Complexity: O(1), as we use a constant amount of space.
1public class Solution {
2 public boolean isPalindrome(String s) {
3 int left = 0, right = s.length() - 1;
4 while (left < right) {
5 while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
6 while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
7 if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
8 return false;
9 }
10 left++;
11 right--;
12 }
13 return true;
14 }
15 public static void main(String[] args) {
16 Solution solution = new Solution();
17 String s = "A man, a plan, a canal: Panama";
18 System.out.println(solution.isPalindrome(s));
19 }
20}The Java solution uses the Character class for checks and transformations. It compares characters from both ends until all characters are checked or a difference is found, returning the appropriate boolean value.
This approach first cleans the input string by removing non-alphanumeric characters and converting all letters to lowercase. It then compares the normalized string to its reverse to determine if it is a palindrome.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), because the cleaned string and its reverse require extra space proportional to n.
1const isPalindrome = function(s)
In JavaScript, this solution uses regular expressions to filter and clean the input and then leverage string manipulation techniques to check if cleaned string equals its reverse.