Valid Palindrome

Q: Valid Palindrome의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 모든 문자를 일정한 횟수만큼 확인하므로 O(n) 시간이 걸립니다. 먼저 정리하는 방식은 복사본을 위해 O(n) 의 추가 메모리를 사용합니다. 두 포인터 방식은 인덱스 두 개만 유지하므로 O(1) 의 추가 메모리를 사용합니다.

Q: 영숫자가 아닌 문자를 무시하면서 회문인지 어떻게 확인하나요?

문자열의 양 끝에 포인터를 하나씩 둡니다. 문자나 숫자가 아닌 문자는 포인터를 이동해 건너뛰고, 두 포인터가 모두 문자나 숫자를 가리키면 소문자로 비교합니다. 포인터가 만날 때까지 비교한 모든 쌍이 일치하면 해당 문자열은 회문입니다.

Q: 빈 문자열은 회문인가요?

맞습니다. 빈 텍스트는 어느 방향으로 읽어도 같으므로, 모든 문자가 무시되는 ?!-_ 와 같은 문자열은 true 를 반환합니다. 두 접근 방식 모두 추가 코드 없이 이 결과를 얻습니다. 정리된 텍스트는 뒤집은 빈 텍스트와 같고, 두 포인터는 서로 다른 문자 쌍을 찾지 못합니다.

Q: 문자열을 뒤집는 대신 투 포인터를 사용하는 이유는 무엇인가요?

반전에는 정리된 복사본과 뒤집힌 복사본이 필요하므로 O(n) 의 추가 메모리가 필요합니다. 두 포인터는 같은 쌍을 제자리에서 비교하며, 첫 번째 불일치에서 멈출 수 있어 몇 단계만으로 끝나는 경우가 많습니다. 면접관은 보통 후속 질문으로 이 버전을 요청합니다.

쉬움투 포인터

+10

문자열 s가 주어집니다. 문자와 숫자만 남기고, 대문자와 소문자를 같은 문자로 취급하여, 남은 내용이 왼쪽에서 오른쪽으로 읽을 때와 오른쪽에서 왼쪽으로 읽을 때 같은지 판단하세요. 같으면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

., !, ?, :, ;, - 또는 _와 같은 그 밖의 모든 문자는 무시합니다. s에 문자나 숫자가 전혀 없다면 아무것도 남지 않으며, 빈 문자열은 회문으로 간주합니다.

함수

isPalindrome(s: string) → boolean

sstring: 확인할 텍스트(문장 부호 포함)
반환값boolean: 대소문자를 무시했을 때 s의 문자와 숫자가 양방향으로 동일하게 읽히면 true

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
s에는 공백 없이 영문자, 숫자 및 문장 부호 . ! ? : ; - _가 포함되어 있습니다.

예제

입력: s = "Was_it_a_car_or_a_cat_I_saw?"
출력: true
설명: 밑줄과 물음표를 없애고 대문자를 소문자로 바꾸면 wasitacaroracatisaw가 되는데, 이는 거꾸로 읽어도 같습니다.

입력: s = "race-a-car"
출력: false
설명: 하이픈이 없으면 텍스트는 raceacar입니다. 오른쪽에서 읽으면 race가 아니라 raca로 시작합니다. 가운데의 e는 거울 짝이 a이므로 답은 false입니다.

입력: s = "Step-on-no-pets!"
출력: true
설명: 유지된 텍스트는 steponnopets입니다. 대문자 S는 대소문자를 구분하지 않으므로 마지막 s와 일치하고, 하이픈과 !는 아무런 역할도 하지 않습니다.

제출 시 숨은 테스트 +25개

후속 질문

정리된 s의 복사본을 만들지 않고 추가 메모리 O(1)로 이를 결정할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

회문 검사는 익숙한 방식입니다. 남겨진 첫 번째 문자는 마지막 문자와 같아야 하고, 두 번째 문자는 끝에서 두 번째 문자와 같아야 하는 식입니다. 이 버전이 까다로운 이유는 비교하는 문자가 s의 서로 대칭되는 인덱스에 있지 않기 때문입니다. 문장 부호가 양쪽에 고르지 않게 흩어져 있습니다. 문장 부호를 먼저 제거하거나, 두 포인터가 서로를 향해 이동하면서 문장 부호를 건너뛰게 할 수 있습니다.

문자열을 정리한 다음, 뒤집은 문자열과 비교합니다

핵심 아이디어

문제에서 실제로 묻는 텍스트를 만드세요. s를 훑으면서 각 문자나 숫자는 소문자로 유지하고, 나머지는 모두 건너뛰세요. Step-on-no-pets!는 steponnopets가 됩니다. 이제 질문은 기본적인 회문 질문입니다. 이 텍스트는 뒤집은 텍스트와 같을까요?

이 방법이 올바른 이유는 정리에 따라 문제에서 무시하라고 한 문자만 제거하고, 대소문자 구분을 무시하라고 한 대로 대소문자를 통일하기 때문입니다. s에 문자나 숫자가 하나도 없으면 정리된 텍스트는 비어 있으며, 빈 텍스트는 뒤집어도 같으므로 특별한 경우를 따로 처리하지 않아도 답은 true입니다.

각 문자는 정리할 때 한 번, 비교할 때 한 번 더 읽으므로 시간 복잡도는 O(n)입니다. 정리한 복사본과 그 복사본을 뒤집은 텍스트에는 O(n)의 추가 메모리가 필요하며, 다음 접근법은 이 비용을 없앱니다.

알고리즘

빈 텍스트 cleaned를 만듭니다.
s의 각 문자가 문자 또는 숫자이면 소문자로 변환하여 추가합니다.
cleaned를 뒤집습니다.
cleaned가 뒤집은 결과와 같은지 여부를 반환합니다.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

문장 부호를 건너뛰는 두 포인터

핵심 아이디어

정리된 복사본은 대칭 위치의 문자를 비교할 수 있도록 마련한 것뿐입니다. s에서 직접 같은 비교를 할 수도 있습니다. left를 첫 번째 인덱스에, right를 마지막 인덱스에 둡니다. 각 단계에서 left가 문장 부호를 가리키면 오른쪽으로 이동하고, right가 문장 부호를 가리키면 왼쪽으로 이동합니다. 두 포인터가 모두 문자나 숫자를 가리키면 소문자로 비교합니다. 일치하지 않으면 false이고, 일치하면 두 포인터를 안쪽으로 한 칸씩 이동합니다.

왜 이것이 같은 검사일까요? 포인터는 양쪽 끝에서 다음으로 남겨진 문자에 항상 멈추므로, (첫 번째 남겨진 문자, 마지막 남겨진 문자), (두 번째 남겨진 문자, 뒤에서 두 번째 남겨진 문자) 등의 쌍을 방문합니다. 이는 뒤집어서 비교할 때 살펴보는 쌍과 정확히 같습니다. Abc-dcbX에서는 첫 번째 쌍이 A와 X이며, 한 번 비교한 뒤 답은 false입니다.

각 단계에서 포인터가 적어도 하나씩 이동하고 두 포인터가 만날 때 멈추므로, 반복문은 최대 n번 실행됩니다. 두 인덱스 외에는 아무것도 저장하지 않으므로 추가 메모리는 O(1)입니다.

알고리즘

left = 0 및 right = n-1로 설정합니다.
left < right인 동안: s[left]가 문자나 숫자가 아니면 left를 증가시키고 계속합니다.
그렇지 않고 s[right]가 문자나 숫자가 아니면 right를 감소시키고 계속합니다.
그렇지 않으면 두 문자를 소문자로 변환해 비교합니다. 서로 다르면 false를 반환하고, 같으면 두 포인터를 모두 안쪽으로 이동합니다.
두 포인터가 만나면 true를 반환합니다.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

함정과 경계 사례

대부분의 버그는 건너뛰는 문자와 대소문자에서 발생합니다.

원시 문자열에서 s[i]와 s[n-1-i]를 비교합니다. 하이픈을 제거하면 a-ba는 회문이지만, 인덱스 1의 -와 원시 문자열에서 대칭인 문자는 인덱스 2의 b입니다.
두 포인터 중 하나만 문장 부호에 있을 때 두 포인터를 모두 이동합니다. 한 번에 한쪽만 건너뛰어야 합니다. 그렇지 않으면 양쪽의 위치가 어긋납니다.
다른 포인터를 지나쳐 실행되는 내부 루프에서 문장 부호를 건너뜁니다. ?!-_에서 제한되지 않은 내부 루프는 문자열의 끝을 벗어납니다. 이동할 때마다 left < right 검사를 수행하세요.
숫자를 무시할 문자로 취급합니다. 0P는 false입니다. 숫자 0은 유지되어 비교되며, 문자 p가 아닙니다.
유지되는 문자가 없을 때 false를 반환합니다. .처럼 문장 부호만 있는 문자열은 정제 후 빈 문자열이 되며, 이는 회문입니다.
12321처럼 숫자만으로 이루어진 문자열은 PHP와 R에서 숫자로 처리될 수 있습니다. 먼저 문자열로 변환하세요.

자주 묻는 질문4

Valid Palindrome의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 모든 문자를 일정한 횟수만큼 확인하므로 O(n) 시간이 걸립니다. 먼저 정리하는 방식은 복사본을 위해 O(n)의 추가 메모리를 사용합니다. 두 포인터 방식은 인덱스 두 개만 유지하므로 O(1)의 추가 메모리를 사용합니다.

영숫자가 아닌 문자를 무시하면서 회문인지 어떻게 확인하나요?

문자열의 양 끝에 포인터를 하나씩 둡니다. 문자나 숫자가 아닌 문자는 포인터를 이동해 건너뛰고, 두 포인터가 모두 문자나 숫자를 가리키면 소문자로 비교합니다. 포인터가 만날 때까지 비교한 모든 쌍이 일치하면 해당 문자열은 회문입니다.

빈 문자열은 회문인가요?

맞습니다. 빈 텍스트는 어느 방향으로 읽어도 같으므로, 모든 문자가 무시되는 ?!-_와 같은 문자열은 true를 반환합니다. 두 접근 방식 모두 추가 코드 없이 이 결과를 얻습니다. 정리된 텍스트는 뒤집은 빈 텍스트와 같고, 두 포인터는 서로 다른 문자 쌍을 찾지 못합니다.

문자열을 뒤집는 대신 투 포인터를 사용하는 이유는 무엇인가요?

반전에는 정리된 복사본과 뒤집힌 복사본이 필요하므로 O(n)의 추가 메모리가 필요합니다. 두 포인터는 같은 쌍을 제자리에서 비교하며, 첫 번째 불일치에서 멈출 수 있어 몇 단계만으로 끝나는 경우가 많습니다. 면접관은 보통 후속 질문으로 이 버전을 요청합니다.

Python

def isPalindrome(s):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "Was_it_a_car_or_a_cat_I_saw?"

기대값

true