LeetCode 125 - Valid Palindrome (Easy)

출처: https://leetcode.com/problems/valid-palindrome/

// LeetCode 125 - Valid Palindrome (Easy)
// https://leetcode.com/problems/valid-palindrome/

// 문제 설명
// 대문자를 소문자로 바꾸고 영숫자가 아닌 문자를 모두 제거했을 때,
// 앞에서 읽으나 뒤에서 읽으나 같으면 팰린드롬이다.
// 문자열 s가 팰린드롬이면 true, 아니면 false를 반환하라.

// 제약 조건
// 1 <= s.length <= 2 * 10^5
// s는 출력 가능한 ASCII 문자로만 구성된다.

// Example 1
// Input : s = "A man, a plan, a canal: Panama"
// Output: true   ("amanaplanacanalpanama")
//
// Example 2
// Input : s = "race a car"
// Output: false  ("raceacar")
//
// Example 3
// Input : s = " "
// Output: true   (영숫자 제거 후 빈 문자열 → 팰린드롬)

// 접근 — 양끝 투 포인터
// 새 문자열을 따로 만들지 않고, 원본을 양 끝에서 좁혀 들어가며 비교한다.
// 1) l(왼쪽)·r(오른쪽) 포인터를 양 끝에 둔다.
// 2) 영숫자가 아닌 문자는 l은 오른쪽으로, r은 왼쪽으로 건너뛴다.
// 3) 둘 다 영숫자에 멈추면 소문자로 바꿔 비교 — 다르면 즉시 false.
// 4) l < r 동안 반복, 끝까지 통과하면 true.
// 시간 O(n), 공간 O(1)

#include <string>
#include <cctype>
using namespace std;

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = (int)s.size() - 1;
        while (l < r) {
            // 영숫자가 아니면 건너뛴다 (unsigned char 캐스팅: 음수 인덱스 UB 방지)
            while (l < r && !isalnum((unsigned char)s[l])) ++l;
            while (l < r && !isalnum((unsigned char)s[r])) --r;
            if (tolower((unsigned char)s[l]) != tolower((unsigned char)s[r]))
                return false;
            ++l;
            --r;
        }
        return true;
    }
};

정리

• 핵심은 영숫자만 추린 새 문자열을 만들지 않고 원본을 양 끝에서 비교한다는 점이다. 별도 버퍼를 쓰면 O(n) 공간이 들지만, 투 포인터로 건너뛰며 비교하면 공간이 O(1)로 떨어진다.
• 영숫자가 아닌 문자(,, ` , : 등)는 비교 대상이 아니므로 isalnum`이 false인 동안 포인터를 그냥 전진/후진시켜 건너뛴다. 두 포인터가 모두 영숫자에 멈췄을 때만 한 글자씩 맞춰 본다.
• isalnum·tolower에 넘기는 인자는 unsigned char로 캐스팅했다. char가 부호 있는 타입인 환경에서 음수 값이 넘어가면 동작이 정의되지 않기 때문이다. ASCII 입력이라도 습관적으로 캐스팅해 두는 게 안전하다.
• 안쪽 while에 l < r 조건을 같이 둔 게 중요하다. " "처럼 영숫자가 하나도 없는 입력에서 포인터가 서로를 지나쳐 인덱스를 벗어나는 걸 막는다. 빈 문자열·공백뿐인 입력도 자연히 true로 처리된다.
• 검증: 예제 3개 모두 통과(MSVC /std:c++17 컴파일·실행).