[LeetCode] 125. valid-palindrome (Easy) 2023/4/27

문제 제목	정답률	난이도
125. valid-palindrome	44.5%	Easy

Valid Palindrome - LeetCode

 

문제 요약

주어진 문자열이 팰린드롬이면 참을, 아니라면 거짓을 반환하라

조건 1) 모든 대문자를 소문자로 바꾸라

조건 2) 숫자와 문자가 아닌 부분은 모두 지워라

조건 3) 펠린드롬이란 앞에서부터 읽어온 것과 뒤에서부터 읽어온 것이 같은 경우를 말한다(좌우대칭)

 

공통풀이

Step1. 대문자를 소문자로 바꾸기 + 숫자와 문자를 제외한 문자열 삭제

Step2. 펠린드롬 판단

 

Step1-1. 대문자를 소문자로 바꾸기 -> string.lower() 함수 이용

 

문자열 대문자로 변경하는 함수	string.upper()
문자열 소문자로 변경하는 함수	string.lower()
문자열의 모든 문자가 대문자인지 확인하는 함수	string.isupper()
문자열의 모든 문자가 소문자인지 확인하는 함수	string.islower()

 

Step1-2. 숫자와 문자를 제외한 문자열 삭제 -> if 이용해서 판단 | 정규식 이용

 

문자열의 모든 문자가 영어나 한글인지 확인하는 함수	string.isalpha()
문자열의 모든 문자가 영어나 한글이나 숫자인지 확인하는 함수	string.isalnum()

 

기본 정규표현식 기호

숫자와 매치	[0-9]	\d
숫자가 아닌것과 매치	[^0-9]	\D
알파벳 문자와 매치	[a-zA-Z]
알파벳 문자+숫자와 매치	[a-zA-z0-9_]	\w
알파벳 문자와 숫자가 아닌것과 매치	[^a-zA-z0-9_]	\W
줄바꿈을 제외한 모든 문자와 매치	.
바로 앞의 문자 반복(0~무한)	*
바로 앞의 문자 반복(1~무한)	+
바로 앞의 문자 특정 횟수만큼 반복	{n}
바로 앞의 문자 특정 횟수 범위 만큼 반복	{n, m}

 

 

Step2. 펠린드롬 판단

 

- 배열의  pop 기능을 이용해 문자로 비교 (pop(0)과 pop() 비교) $O(n^{2})$

- 데크 자료형을 이용해 최적화 (popleft()와 pop() 비교) $O(n)$

이유 :  pop(0)의 시간복잡도는 $O(n)$ 이지만 popleft()는 양방향 링크드리스트로 구현되어 있어 시간복잡도가 $O(1)$ 이기 때문이다.

- 문자열 슬라이싱 이용해서 문자열 통째로 비교

 

 

구현

def isPalindrome(self, s:str) -> bool:
    ## 소문자로 변환
    s.lower()
    ## 숫자, 알파벳만 남기기
    s=re.sub(['^a-z0-9']. '', s)
    
    #슬라이싱 이용해서 문자열을 뒤집은 후 값이 같은지 확인
    return s==s[::-1]