Skip to main content

Valid Palindrome

Valid Palindrome

문장이 대문자를 모두 소문자로 변환하고, 알파벳과 숫자가 아닌 문자를 모두 제거한 후에도 앞으로 읽으나 뒤로 읽으나 동일한 경우, 그 문장은 팰린드롬입니다. 문자열 s가 주어졌을 때, 이것이 팰린드롬이면 true를, 그렇지 않으면 false를 반환합니다.

입출력 예제

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

접근 방향

먼저 문자열을 리스트로 만들어 한 글자씩 순회하며 대문자는 소문자로 바꾸어 다른 배열에 추가하고 숫자와 소문자일 경우 그대로 배열에 추가합니다. 이렇게 필터 작업을 거쳤다면 해당 배열에는 소문자와 숫자만 남을 것이고 이 배열에서 투 포인터를 활용하여 하나의 포인터는 앞에서 뒤로 진행하고 다른 하나는 뒤에서 앞으로 진행하면서 각 포인터가 가르키는 배열의 요소와 비교하여 동일하면 넘어가고 동일하지 않을 경우 False를 반환하도록 합니다.

나의 풀이

import re
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""

# re 라이브러리를 사용해 정규식 패턴을 다음과 같이 정의합니다.
# 아래 정규식에 의하면 소문자, 대문자, 숫자만을 허용합니다.
p = re.compile('[a-zA-Z0-9]')

# 새로운 배열을 생성합니다.
l = []

# [필터 작업]
# 문자열을 배열로 변환하여 한 글자씩 추출하며 순회합니다.
for word in list(s):
# 만약 추출한 문자가 위 정규식에 해당할 경우이면서
if p.match(word):
# 문자가 대문자일 경우 소문자로 변경합니다.
if word.isupper():
word = word.lower()
# 문자를 배열에 요소로 추가합니다.
l.append(word)


start = 0 # 앞에서부터 뒤로 진행할 포인터
end = -1 # 뒤에서부터 앞으로 진행할 포인터

# l의 길이가 홀수일 경우 두 포인터가 중간 요소 전까지 순회
# 짝수일 경우 두 포인터가 만나기 전까지 순회
while start <= ((len(l) // 2) - 1):
# 만약 두 요소가 동일하다면 아래 로직 수행
if l[start] == l[end]:
pass
else: # 그렇지 않다면 False 반환, 종료
return False

# 포인터 이동
start += 1
end -= 1
return True