[python/leetcode] 125번 valid-palindrome 문제 풀이

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

Valid Palindrome - LeetCode

 

valid-palindrome

문제 요약 : 앞으로 읽어도 거꾸로 읽어도 같은 문자열인지 확인

 

기본 로직은 다음과 같다.

1. 각각의 문자를 알파벳이나 숫자인지 확인한다
2. 맞을 경우 배열에 (소문자로) 넣는다
3. 배열의 왼쪽 절반과 (뒤집은) 오른쪽 절반을 비교한다.

# https://leetcode.com/problems/valid-palindrome/
import re

def isPalindrome(s: str) -> bool:
  result = []

  for c in s:
  	# 문자/숫자만 result에 (소문자로) 넣기
    if re.compile(r'\d|[a-zA-Z]').search(c):
       result.append(c.lower())

  # 왼쪽 절반과, 뒤집은 오른쪽 절반을 비교
  mid = len(result) // 2
  left = list(result[0:mid])
  right = list(result[(mid if len(result) % 2 == 0 else mid + 1):])
  right.reverse()
    
  # print(left)
  # print(right)
    
  return left == right

print(isPalindrome(s='race a car'))
print(isPalindrome(s="A man, a plan, a canal: Panama"))
print(isPalindrome(s=" "))

 

문자인지 숫자인지 검증하는 부분은 정규표현식을 사용했다.

import re

c = 'a'

result = re.compile(r'\d|[a-zA-Z]').search(c)

print(result)
# <re.Match object; span=(0, 1), match='a'>

re는 정규표현식을 쓸 수 있는 파이썬 라이브러리로 import re를 통해 사용한다.

만약에 c가 ‘?’ 라는 문자열이라면 None이 리턴된다.

\d는 숫자를 얘기한다. 문자는 \w를 쓰려고 했는데 '_' 같은 것도 문자로 인식하기 때문에 알파벳만 넣었다. 

이렇게 쓸거면 차라리 [a-zA-Z0-9]로 쓰는 편이 더 나았겠다. 

 

 

정규표현식을 쓰지 않고 isalnum이라는 메서드를 사용할 수도 있다.

알파벳과 숫자로 이루어져 있는지 확인할 수 있다.

print('abc123'.isalnum()) # True
print('#'.isalnum()) # False

 

 

왼쪽 절반을 구할 때 특이했던건 배열을 슬라이스 하면 문자열이 나온다는 것이다.

( js에서는 배열을 slice 하면 배열이 나온다. )

result = 'abcba'
left = result[0:len(result) // 2]
print(left) # ab
print(type(left)) # <class 'str'>

 

그래서 다시 list 함수로 감싸줬다.

left = list(result[0:len(result) // 2])

 

 

보완한다면…

오른쪽 절반을 구하는 부분을 너무 복잡하게 구현한 것 같다.

right = list(result[(mid if len(result) % 2 == 0 else mid + 1):])
right.reverse()

단순히 절반이아니라, 전체 길이가 홀수일 경우 중간 + 1 부터 나머지를 구해야 해서 코드가 좀 복잡해졌다.

 

다른 풀이를 보니 굳이 절반을 구할 필요가 없고, 전체와 전체를 뒤집은 것을 비교해서 일치하는지를 확인해도 됐다…!

이 경우 리스트를 reverse를 쓰는 것보다 문자열을 슬라이싱 하는 게 더 빠르기 때문에

불필요한 값을 제거한 문자열을 만들어 이를 뒤집은 것과 비교할 수 있다.

s == s[::1]

js에서 문자를 뒤집으려면 각각을 split해서 배열로 만들고, reverse로 뒤집은 다음, join으로 다시 문자열로 만들어 줄텐데

파이썬에서는 [::1]로 간단히 문자열을 뒤집을 수 있다.