[LeetCode 125] Valid Palindrome (Java)

---

풀이

이 문제는 문자열 s가 주어졌을 때, s에서 영문자나 숫자가 아닌 문자들을 제거하고 모든 문자를 소문자로 변경한 뒤, 이 문자열이 팰린드롬인지 판단하는 문제이다.

정말 단순하게 s.toLowerCase().replaceAll("[^a-z0-9]", "")로 문제의 요구대로 문자열을 조작한 뒤, 팰린드롬인지 판단하는 것도 가능하다.

하지만 이는 문자열을 새로 만들기 때문에, 오버헤드가 생길 수 밖에 없다. 따라서 기존의 문자열 s를 그대로 이용하되, 영문자나 숫자가 아니라면 건너뛰고, 그렇지않다면 소문자로 변경 후 비교해주면 될 것이다.

이제, 팰린드롬을 판별하는 알고리즘에 대해 살펴보자. 팰린드롬은 반복문과 재귀함수를 이용해 구현이 가능하다.

1. 반복문 이용

먼저, 반복문을 이용해 구현해보도록 하자. 반복문으로 구현시에는 단순히 for루프를 이용하는 것 보다, 투포인터 기법을 이용하는 것이 유리하다.

왜냐하면, for루프에서는 0부터 가운데 인덱스까지 반복하며, 가운데 인덱스에 대칭되는 원소들을 비교해나가야 하는데, 자칫 반복 조건에 대해 실수할 여지가 있기 때문에, 좀 더 단순한 투포인터 기법을 이용하는 것이 좋다.

그저, 한 포인터는 시작부터 오른쪽으로 이동하고, 다른 포인터는 끝에서부터 왼쪽으로 이동하면서 비교해나가면 되고, 두 포인터가 같은 위치를 가리킨다면 더 이상 두 문자가 같은지 비교하는 연산을 반복할 이유가 없어진다.

이제 이를 코드로 옮기면 다음과 같다.

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            char ch1 = s.charAt(i), ch2 = s.charAt(j);
            if (!Character.isLetterOrDigit(ch1)) {
                i++;
            } else if (!Character.isLetterOrDigit(ch2)) {
                j--;
            } else {
                if (Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
                    return false;
                i++;
                j--;
            }
        }
        return true;
    }
}

2. 재귀함수 이용

재귀함수를 이용해 구현하는 것도 위의 반복문을 이용하는 것과 유사하다. 가운데 값을 기준으로 대칭되는 쌍을 비교해 나가면서 팰린드롬인지 판단하면 된다는 의미이다.

이를 코드로 옮기면 다음과 같다.

class Solution {
    public boolean isPalindrome(String s) {
        return isPalindrome(s, 0, s.length() - 1);
    }

    public boolean isPalindrome(String s, int i, int j) {
        if (i >= j) 
            return true;
        
        char ch1 = s.charAt(i), ch2 = s.charAt(j);
        if (!Character.isLetterOrDigit(ch1))
            return isPalindrome(s, i + 1, j);
        if (!Character.isLetterOrDigit(ch2))
            return isPalindrome(s, i, j - 1);
        if (Character.toLowerCase(ch1) != Character.toLowerCase(ch2))
            return false;
        return isPalindrome(s, i + 1, j - 1);
    }
}

3. 문자열 직접 조작

위에서 언급했듯, 문자열을 직접 조작하여 문제를 해결할 수도 있다. 오버헤드가 심하겠지만 이를 코드로 옮기면 다음과 같다.

class Solution {
    public boolean isPalindrome(String s) {
        String filtered = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        String reversed = new StringBuilder(filtered).reverse().toString();
        return filtered.equals(reversed);
    }
}