(String, Easy) Valid Palindrome

https://leetcode.com/problems/valid-palindrome/description/

간단하게 풀려면 replaceAll 정규식으로 알파벳, 숫자만 남기고 toLowerCase 한다.

이게 팰린드롬인지 확인하는거야 StringBuilder 써서 reverse 해도 되고,
아니면 절반만큼 순회하면서 left, right가 같은지 체크해도 되고.

class Solution {
    public boolean isPalindrome(String s) {
        
        s = s.replaceAll("[^a-zA-Z0-9]", "");
        s = s.toLowerCase();

        for (int i=0; i<s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) {
                return false;
            }
        }

        return true;
    }
}

정규식, lowercase, N/2회 반복 모두 논리적으로는 O(N)이긴 한데
포인터 땡겨가면서 불필요한 문자 무시하고 left == right 체크하면 루프 빈도를 줄일 수 있음.

class Solution {
    public boolean isPalindrome(String s) {
        
        int left = 0;
        int right = s.length() - 1;

        while (left <= right) {
            char lc = Character.toLowerCase(s.charAt(left));
            char rc = Character.toLowerCase(s.charAt(right));

            if (!Character.isAlphabetic(lc) && !Character.isDigit(lc)) {
                left++;
            } else if (!Character.isAlphabetic(rc) && !Character.isDigit(rc)) {
                right--;
            } else {

                if (lc != rc) {
                    return false;
                }
                left++;
                right--;
            }
        }

        return true;
    }
}