Очередная задачка уровня Easy, но с довольно низким показателем Acceptance (44.4%). Что выражается в достаточно обширном наборе граничных случаев, некоторые из которых делают больно
Было желание сделать за один проход по исходной строке (без выделения дополнительно памяти). Вроде даже получилось, если ориентироваться на статистику запуска с LeetCode.
class Solution {
private static final int LETTER_CASE_SHIFT = 32;
public boolean isPalindrome(String s) {
if (s.length() == 1) return true;
char a, b;
int mid = (s.length() - 1) >>> 1;
for (int i = 0, j = s.length() - 1; i <= mid; i++, j--) {
a = s.charAt(i);
b = s.charAt(j);
while (isNotAlphaNumeric(a) && i < j) {
a = s.charAt(++i);
}
while (isNotAlphaNumeric(b) && i < j) {
b = s.charAt(--j);
}
if (isComparable(a, b)) {
if (!equalsIgnoreCase(a, b)) {
return false;
}
} else {
return false;
}
mid = (i + j) / 2;
}
return true;
}
private static boolean equalsIgnoreCase(char a, char b) {
return a == b
|| a - LETTER_CASE_SHIFT == b
|| a == b - LETTER_CASE_SHIFT;
}
private static boolean isComparable(char a, char b) {
return (isLetter(a) && isLetter(b))
|| (!isLetter(a) && !isLetter(b));
}
private static boolean isLetter(char ch) {
return 'a' <= ch && ch <= 'z'
|| 'A' <= ch && ch <= 'Z';
}
private static boolean isNotAlphaNumeric(char ch) {
return !isLetter(ch) && ('0' > ch || ch > '9');
}
}
Success: Runtime:2 ms, faster than 99.92% of Java online submissions. Memory Usage:42.3 MB, less than 87.41% of Java online submissions.
Ссылка на решение на Гитхаб.
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.
https://leetcode.com/problems/valid-palindrome/