LeetCode Top Interview 150) Valid Palindrome

EBAB!·2023년 8월 28일
0

LeetCode

목록 보기
9/35

Question

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.
class Solution:
    def isPalindrome(self, s: str) -> bool:




아스키코드로 표현가능한 문자로만 이루어진 문자열 s가 주어집니다. 여기서 알파벳과 숫자를 제외했을 때, 팰린드롬을 이루는지 여부를 bool값으로 반환하는 문제입니다.

  • 펠린드롬 문자열은 쉽게 말해 중앙을 기준으로 대칭을 이루는 문자열입니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        start_idx,end_idx = 0,len(s)-1

        while start_idx < end_idx:
            while not s[start_idx].isalnum() and start_idx < end_idx: start_idx +=1
            while not s[end_idx].isalnum() and start_idx < end_idx : end_idx -=1

            if s[start_idx].lower() != s[end_idx].lower():
                return False
            start_idx += 1    
            end_idx -= 1
        return True
            
  • start_idx, end_idx : 대칭을 확인할 앞, 뒤 문자의 인덱스 변수입니다.
  • 대칭을 확인하는 과정이므로 while문의 조건은 서로의 인덱스가 지나치지 않는 것으로 합니다.
    • 중간에 알파벳이나 숫자가 아닌 문자열이면 인덱스 값을 올리거나 내려야 하기 때문에 인덱스는 대칭이 아닐 수 있기 때문입니다.
  • 숫자나 알파벳이 나오기 전까지 start_idx는 올리고 end_idx값은 내리며 조정합니다.
  • 알파벳이라면 소문자로 비교하므로 lower()을 통해 소문자로 변환한 값이 같은지 비교합니다.
    • 이 문자가 알파벳이 아니라면 원래 문자를 반환하므로 숫자를 신경쓰지 않아도 됩니다.
    • 다르다면 대칭이 아니므로 False를 반환합니다.
    • 같다면 다음 문자를 비교하기위해 각 인덱스 값을 1씩 조정합니다.
  • while문을 탈출했다면 모든 알파벳,숫자 문자에 대해 대칭을 이루는 상황이므로 True를 반환합니다.


조건문에서 최대 길이가 200,000까지 나오기 때문에 O(n)으로 해결해야 하는 것을 알 수 있었습니다.

알파벳과 숫자 외의 문자를 지나쳐야 하는 부분에서 인덱스의 대칭이 깨지므로 최소 두 개의 인덱스 변수가 필요하다는 방향을 잡았습니다.

약간의 편법(?)으로 풀었던 부분을 고백하자면 예외 부분을 크게 신경쓰지 않고 코드를 작성했습니다. 문자열의 길이가 1이거나 알파벳이나 숫자가 아닌 문자열로 이루어져 있거나..
테스트케이스를 통해 고쳐야지 했는데 잘 통과했네요 하핳

profile
공부!

0개의 댓글

Powered by GraphCDN, the GraphQL CDN