Palindrome String

Q: 문자열이 회문인지 어떻게 확인하나요?

첫 번째 문자를 마지막 문자와 비교하고, 두 번째 문자를 끝에서 두 번째 문자와 비교하는 식으로 가운데를 향해 진행합니다. 어느 한 쌍이라도 다르면 문자열은 회문이 아닙니다. 양쪽 끝에서 시작해 가운데를 향해 이동하는 두 인덱스를 사용하면 한 번의 순회로 이를 수행할 수 있습니다.

Q: 추가 메모리 없이 회문인지 확인할 수 있나요?

네. 두 포인터 검사는 문자를 제자리에서 읽고 두 개의 인덱스를 저장하므로 추가 공간을 O(1) 사용합니다. s 를 뒤집은 문자열과 비교하는 방식은 코드를 더 짧게 작성할 수 있지만, n 개의 문자로 이루어진 두 번째 문자열을 만듭니다.

Q: 회문 문자열인지 확인하는 시간 복잡도는 얼마인가요?

길이가 n 인 문자열의 경우 O(n) 입니다. 두 포인터 검사는 최대 n / 2 번 비교하고 첫 번째 불일치에서 멈추므로, coddy 는 한 번 비교합니다.

Q: 단일 문자가 회문인가요?

네, 양방향으로 읽어도 같습니다. 두 포인터 루프에서 left 와 right 는 모두 인덱스 0에서 시작하고, 루프는 실행되지 않으며, 함수는 true 를 반환합니다.

입문투 포인터 배열과 문자열

+10

문자열은 왼쪽에서 오른쪽으로 읽을 때와 오른쪽에서 왼쪽으로 읽을 때 동일하면 회문입니다. 예를 들어 level이 있습니다. 소문자 영어 문자로 이루어진 문자열 s를 받아 s가 회문이면 true를, 그렇지 않으면 false를 반환하는 함수를 작성하세요.

함수

isPalindrome(s: string) → boolean

sstring: 확인할 소문자 문자열
반환값boolean: s가 양방향으로 똑같이 읽힐 때 참

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
s에는 소문자 영어 알파벳(a부터 z까지)만 포함됩니다.

예제

입력: s = "racecar"
출력: true
설명: 바깥쪽부터 안쪽으로 비교하세요: r과 r, a와 a, c와 c. 가운데의 e는 짝이 없으며 짝이 필요하지 않으므로 답은 true입니다.

입력: s = "abba"
출력: true
설명: 길이가 짝수이면 모든 문자에 짝이 있습니다. 두 a는 서로 짝을 이루고 두 b도 서로 짝을 이루므로, 답은 true입니다.

입력: s = "coddy"
출력: false
설명: 첫 글자 c와 마지막 글자 y가 이미 다르므로 coddy는 회문이 아니며 답은 false입니다.

후속 질문

공백과 문장 부호를 건너뛰고 대소문자를 구분하지 않도록 두 포인터를 어떻게 변경하면 Was it a car or a cat I saw가 회문으로 판정될까요?

힌트

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

3개 중 0개 열림

풀이

회문은 뒤집은 문자열과 같으므로, 뒤집은 문자열을 만들어 비교할 수 있습니다. 복사본은 필요하지 않습니다. 첫 번째 문자는 마지막 문자와, 두 번째 문자는 끝에서 두 번째 문자와 일치해야 하는 식입니다. 두 인덱스를 안쪽으로 이동시키며 제자리에서 각 쌍을 검사하면 첫 번째 불일치에서 멈춥니다.

문자열과 그 역순을 비교합니다

핵심 아이디어

s를 뒤집어 비교하세요. racecar를 뒤집어도 racecar이고, coddy를 뒤집으면 yddoc입니다. 문자열은 뒤집은 문자열과 같을 때만 양방향으로 동일하게 읽힙니다.

시간 복잡도는 O(n)이지만, 뒤집은 복사본을 만드는 데 O(n)의 추가 공간이 필요합니다. n = 5 × 10^4일 때 문자 50,000개입니다. 작업도 항상 문자열 전체를 처리합니다. coddy는 첫 글자와 마지막 글자만으로 판별할 수 있지만, 그래도 다섯 글자를 모두 먼저 뒤집습니다.

알고리즘

언어의 역순 함수나 마지막 문자부터 첫 문자까지 반복하는 루프를 사용해 s를 뒤집은 문자열을 만듭니다.
뒤집은 문자열을 s와 비교합니다.
두 문자열이 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

def isPalindrome(s):
    return s == s[::-1]

양쪽 끝에서 시작하는 두 포인터

핵심 아이디어

역순으로 바꾸면 인덱스 i가 인덱스 n-1-i로 이동하므로, 모든 i에 대해 s[i]가 s[n-1-i]와 같을 때에만 s는 자신의 역순과 같습니다. 이 조건에서는 각 쌍이 두 번 나타나므로 왼쪽 절반만 확인하면 충분합니다. racecar에서 쌍은 (0, 6), (1, 5), (2, 4)입니다. 인덱스 3의 가운데 e에는 짝이 필요하지 않습니다.

처음으로 서로 다른 쌍이 발견되면 답이 false임이 증명되므로, coddy는 비교 한 번으로 판별됩니다. 비교는 최대 n / 2번 수행되며, 시간 복잡도는 O(n)이고 인덱스 두 개를 사용하므로 공간 복잡도는 O(1)입니다. R은 먼저 문자열을 문자 코드 벡터로 읽으며, 이 작업에는 O(n)의 비용이 듭니다.

알고리즘

left = 0으로 설정하고 right = n-1로 설정합니다.
left < right인 동안 s[left]와 s[right]를 비교합니다.
서로 다르면 false를 반환합니다.
그렇지 않으면 left에 1을 더하고 right에서 1을 뺀 다음 반복합니다.
포인터가 만나거나 교차하면 모든 쌍이 일치한 것이므로 true를 반환합니다.

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

함정과 경계 사례

한 쌍이 일치하는 즉시 true를 반환하는 것. abca는 바깥쪽 쌍을 통과하고 안쪽 쌍에서 실패하므로, true는 반복문이 끝난 뒤에만 반환됩니다.
right를 n-1이 아닌 n에서 시작하는 것. 그러면 끝을 넘어 읽게 됩니다(C에서는 종료 문자 '\0'을 읽습니다). Lua와 R에서는 인덱스가 1부터 n까지이므로, 이 언어들에서는 right가 실제로 n에서 시작합니다.
C에서 ==로 문자열을 비교하는 것. reversed == s는 두 포인터를 비교하므로 복사본의 경우 false입니다. strcmp를 사용하세요.
result = result + ch로 역순 문자열을 만드는 것. 각 단계마다 지금까지의 문자열을 복사하므로, 문자 50,000개에 대해 약 1.25 × 10^9번의 문자 복사가 발생합니다.
Swift 문자열을 정수로 인덱싱하는 것: 컴파일되지 않습니다. s.utf8을 순회하거나 문자를 배열에 복사하세요.

자주 묻는 질문4

문자열이 회문인지 어떻게 확인하나요?

첫 번째 문자를 마지막 문자와 비교하고, 두 번째 문자를 끝에서 두 번째 문자와 비교하는 식으로 가운데를 향해 진행합니다. 어느 한 쌍이라도 다르면 문자열은 회문이 아닙니다. 양쪽 끝에서 시작해 가운데를 향해 이동하는 두 인덱스를 사용하면 한 번의 순회로 이를 수행할 수 있습니다.

추가 메모리 없이 회문인지 확인할 수 있나요?

네. 두 포인터 검사는 문자를 제자리에서 읽고 두 개의 인덱스를 저장하므로 추가 공간을 O(1) 사용합니다. s를 뒤집은 문자열과 비교하는 방식은 코드를 더 짧게 작성할 수 있지만, n개의 문자로 이루어진 두 번째 문자열을 만듭니다.

회문 문자열인지 확인하는 시간 복잡도는 얼마인가요?

길이가 n인 문자열의 경우 O(n)입니다. 두 포인터 검사는 최대 n / 2번 비교하고 첫 번째 불일치에서 멈추므로, coddy는 한 번 비교합니다.

단일 문자가 회문인가요?

네, 양방향으로 읽어도 같습니다. 두 포인터 루프에서 left와 right는 모두 인덱스 0에서 시작하고, 루프는 실행되지 않으며, 함수는 true를 반환합니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

s = "racecar"

예상 출력

true