[LeetCode] 125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama"
is a palindrome."race a car"
is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Thought process:
Two pointers.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public boolean isPalindrome(String s) { int i = 0; int j = s.length() - 1; while (i < j) { while (i < s.length() && !Character.isLetterOrDigit(s.charAt(i))) { i++; } while (j >= 0 && !Character.isLetterOrDigit(s.charAt(j))) { j--; } if (i > j) { return true; } if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) { return false; } i++; j--; } return true; } } |
Time complexity: O(n).
Comments
Post a Comment