문제

Palindrome이란 모든 대문자를 소문자로 변환하고 숫자 또는 알파벳이 아닌 모든 문자를 제거한 뒤 문자열이 맨 앞과 맨 뒤부터 차례로 읽었을 때 앞의 문자와 뒤의 문자가 모두 동일한 문자열이다. 즉 abba와 같이 문자열의 중앙을 기준으로 대칭을 이루는 문자열이다. 문제는 문자열 s가 주어졌을 때 해당 문자열이 Palindrome인지 판별하는 문제이다. 이 때, 문자열 s는 Alphanumeric(알파벳과 숫자로 이루어진)문자열이아닌 출력가능한 ASCII 문자로 이루어져있다.

풀이

문자열이 대칭으로 이루어져있어야하기 때문에 양쪽 끝에서부터 대칭이되는 위치의 문자가 동일한지 판별해야하므로 Two Pointer를 사용하였다. 알고리즘 순서는 다음과 같다.

1. 문자열에 포함된 알파벳을 모두 소문자로 변환한다.
2. left = 0, right = s.length() - 1부터 left < right일 때까지 반복
3. left에 해당하는 문자가 Alphanumeric이 아니면 left++ 한 후 2번 과정부터 실행
4. right에 해당하는 문자가 Alphanumeric이 아니면 right-- 한 후 2번 과정부터 실행
5. left에 해당하는 문자와 right에 해당하는 문자가 일치하지 않으면 return false
6. left++, right-- 후 2번 과정부터 실행

Two Pointer를 사용하여 시간복잡도는 $O(n)$이며 공간복잡도는 $O(1)$으로 가장 적절한 해결방법인 것같다.

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (!isAlphanumeric(s.charAt(left))) {
                left++;
            } else if (!isAlphanumeric(s.charAt(right))) {
                right--;
            } else if (s.charAt(left) != s.charAt(right)) {
                return false;
            } else {
                left++;
                right--;
            }
        }

        return true;
    }

    private boolean isAlphanumeric(char ch) {
        return ('0' <= ch && ch <= '9') || ('a' <= ch && ch <= 'z');
    }
}

다른 풀이

위 풀이보다 더 개선할 것이 생각나지 않아 다른 Solution들을 확인해보았다. 마찬가지로 나와 같은 Two Pointer를 사용하여 문제를 해결하였다.

그동안 쓸일이 없어서 몰랐는데 다른 Solution을 보고 알게된 것은 Character 클래스에 문자가 알파벳, 문자, 숫자 등 판별할 수 있는 함수를 제공하고 있었다.

이를 활용해 맨 처음에 문자열을 모두 소문자로 변환하는 대신 반복문 안에서 해당 문자가 Alphanumeric 인 경우에만 소문자로 변환하도록 하면 n번의 탐색 횟수를 줄일 수 있을것 같아 시도해보았다. 하지만 테스트 케이스의 문자열 길이가 최대 200,000이라 그런지 차이는 없었다.

class Solution {
    public boolean isPalindrome(String s) {
        // s = s.toLowerCase();
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (!isAlphanumeric(s.charAt(left))) {
                left++;
            } else if (!isAlphanumeric(s.charAt(right))) {
                right--;
            } else {
                char leftCh = Character.toLowerCase(s.charAt(left));
                char rightCh = Character.toLowerCase(s.charAt(right));

                if (leftCh != rightCh) {
                    return false;
                }

                left++;
                right--;
            }
        }

        return true;
    }

    private boolean isAlphanumeric(char ch) {
        return Character.isAlphabetic(ch) || Character.isDigit(ch);
    }
}