125. Valid Palindrome

Published at 2026-11-09

https://leetcode.com/problems/valid-palindrome/description/

문제 요약: 주어진 문자열 s에서, 다음 과정(Alphanumeric)을 거친 문자열이 팰린드롬인지 판단.

  • 대문자는 모두 소문자로
  • 영문과 숫자가 아닌 문자는 모두 제거

풀이

직관

  1. 우선 팰린드롬을 판단해야 하니, 첫글자-끝글자부터 각각 시작해서 하나씩 비교하는 과정은 꼭 필요하겠다.
  2. 유효한 글자인 Alphanumeric(영숫자문자)만 비교해야 하기 때문에, 1번 과정을 할 때, 유효하지 않은 글자면 패스하고 다음 순서로 넘기는 과정을 추가해야겠다.

풀이 과정

  1. 투포인터 방식으로 i, j 를 처음과 끝 인덱스에서 시작하도록 했다.
  2. 영숫자를 판단하기 위해 처음에는 아스키코드를 이용한 대소비교를 하려 그랬는데(.chr()), ai한테 관련 내장함수가 있는지 물어보니 .isalnum()이라는 함수를 알려줬다. isalnum()은 영숫자면 true, 그렇지않으면 false를 리턴한다. 이를 이용해 코드를 많이 줄일 수 있었다.
  3. 2번까지만 했을 경우, 주어진 s가 “ “으로 들어오는 경우를 커버하지 못한다. 0으로 시작한 i가, 공백을 만나기때문에 비교를 패스하고 다음 인덱스로 넘어가려 하는데, s는 길이 1짜리라 s[1]이 존재하지 않기 때문에 인덱스 범위 초과 에러가 난다.
  4. 때문에 i가 j보다 앞 인덱스인걸 보장하도록 해야했다. i를 증가시킬때(j를 감소시킬때도 마찬가지) i 가 j보다 크거나 같은 상황이 온다면, 이미 앞 과정에서 다 통과한것이기 때문에 이 경우 true를 리턴한다.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 1. 문자열의 처음과 끝에서 각각 시작하는 인덱스를 이용한다.
        # 2. 인덱스는 서로 중앙으로 오면서, 소문자로 변환 & 필요없는 문자는 제거한다.
        # 3. 2번 과정에서, 비교에 유효한 문자(소문자)를 얻어내 둘을 비교한다.

        i, j = 0, len(s)-1
        while i <= j:
            left_char_lower, right_char_lower = s[i].lower(), s[j].lower()
            while not left_char_lower.isalnum():
                i += 1
                if i >= j:
                    return True
                left_char_lower = s[i].lower()
            while not right_char_lower.isalnum():
                j -= 1
                if i >= j:
                    return True
                right_char_lower = s[j].lower()
            
            if left_char_lower == right_char_lower:
                i += 1
                j -= 1
                continue
            else:
                return False
        return True
  1. 최종적으로 이렇게 제출하고 통과했으나, if i >= j: 이 조건을 isalnum() 비교하는 while문에 넣어도 된다.
  2. 또, 처음에는 아스키 코드 비교를 위해 s[n]형태를 많이 써서 left_char 라는 변수로 관리했었는데, 그 부분이 빠지기도 했고 마지막에 문자가 같은지 비교할때 결국 대소문자 상관없이 둘이 같은 알파벳인지만 비교하면 되기 때문에, lower()는 마지막에 비교하는 순간만 써도된다. 5번, 6번 내용으로 코드를 더 줄여보면 다음과 같다.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 1. 문자열의 처음과 끝에서 각각 시작하는 인덱스를 이용한다.
        # 2. 인덱스는 서로 중앙으로 오면서, 소문자로 변환 & 필요없는 문자는 제거한다.
        # 3. 2번 과정에서, 비교에 유효한 문자(소문자)를 얻어내 둘을 비교한다.

        i, j = 0, len(s)-1
        while i <= j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            
            if s[i].lower() == s[j].lower():
                i += 1
                j -= 1
                continue
            else:
                return False
        return True

시간복잡도: O(n)