Valid Palindrome

문제

주어진 문자열 s가 팰린드롬(앞뒤로 읽어도 똑같은 문자열)인지 판별하는 프로그램을 작성하는 문제입니다. 단, 문자열에서 영문자와 숫자만 고려하며 대소문자는 구분하지 않습니다.

• 입력: 인쇄 가능한 ASCII 문자로 이루어진 문자열 s (1 <= s.length <= 2 * 10^5)
• 출력: 팰린드롬이면 true, 아니면 false 반환

링크: https://leetcode.com/problems/valid-palindrome

풀이 1: StringBuilder를 활용한 문자열 정제 및 비교

정규 표현식(Regex)에 의존하지 않고, 아스키코드(ASCII) 값을 직접 활용하여 유효한 문자만 걸러낸 뒤 한 번에 비교하는 직관적인 풀이입니다.

• 문자열 정제 (알파벳 및 숫자 필터링):
  • 입력 문자열을 순회하며 소문자나 숫자인 경우 그대로 StringBuilder에 추가합니다.
  • 대문자인 경우 아스키코드 연산(c - 'A' + 'a')을 통해 소문자로 변환하여 추가합니다.
  • 이 외의 공백이나 특수 문자는 무시되므로 알파벳과 숫자만 남게 됩니다.
• 팰린드롬 판별:
  • 정제가 완료된 문자열을 뒤집은 문자열(sb.reverse().toString())과 equals 메서드로 비교하여 결과를 반환합니다.

코드 1

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c >= 'a' && c <= 'z' || c >= '0' && c <= '9') {
                sb.append(c);
            } else if (c >= 'A' && c <= 'Z') {
                sb.append((char)(c - 'A' + 'a'));
            }
        }

        return sb.toString().equals(sb.reverse().toString());
    }
}

풀이 2: 투 포인터(Two Pointers)를 활용한 공간 복잡도 O(1) 최적화

새로운 문자열 객체를 생성하지 않고, 원본 문자열의 양 끝에서부터 인덱스를 좁혀가며 직접 문자를 비교하는 최적화된 풀이입니다.

• 포인터 설정: start는 문자열의 맨 앞(0), end는 맨 뒤(length - 1)에서 시작합니다. 두 포인터가 교차할 때까지(start <= end) 반복합니다.
• 유효한 문자 탐색:
  • Character.isLetterOrDigit 내장 함수를 사용하여 영문자나 숫자가 아닐 경우, 해당 포인터를 한 칸 이동(start++ 또는 end--)시키고 다음 반복으로 넘어갑니다.
• 팰린드롬 비교:
  • 양쪽 포인터가 모두 유효한 문자를 가리킬 때, 두 문자를 소문자로 통일(Character.toLowerCase)하여 비교합니다.
  • 만약 다르면 팰린드롬이 아니므로 즉시 false를 반환합니다.
  • 같다면 두 포인터를 모두 한 칸씩 안쪽으로 좁히고(start++, end--) 검사를 계속합니다.
• 종료 조건: 두 포인터가 무사히 교차하면 팰린드롬 조건을 완벽히 만족한 것이므로 true를 반환합니다.

코드 2

class Solution {
    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
            return true;
        }

        int start = 0, end = s.length() - 1;
        
        while (start <= end) {
            char cs = s.charAt(start);
            char ce = s.charAt(end);
            
            // 왼쪽 포인터가 영문자/숫자가 아니면 건너뜀
            if (!Character.isLetterOrDigit(cs)) {
                start++;
            } 
            // 오른쪽 포인터가 영문자/숫자가 아니면 건너뜀
            else if (!Character.isLetterOrDigit(ce)) {
                end--;
            } 
            // 둘 다 영문자/숫자인 경우 비교
            else { 
                if (Character.toLowerCase(cs) != Character.toLowerCase(ce)) {
                    return false;
                }
                start++;
                end--;
            }
        }

        return true;
    }
}

알고리즘 분류

문자열 (String), 투 포인터 (Two Pointers), 구현 (Implementation)