•
•
문제 설명 : 제공된 문자열에서 대소문자 상관 없이 영숫자만 확인하였을 때 회문인지 여부를 반환
•
풀이 방법
◦
우선 영숫자만 확인해야하기 때문에, 영숫자의 갯수를 먼저 구하였다.
▪
영숫자가 없다면 바로 True 반환
◦
영숫자가 존재한다면, 양쪽에서 커서를 옮기며 비교하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def isPalindrome(self, s: str) -> bool:
# 영숫자인지 확인하는 함수
def is_alpha_or_number(ch: str) -> bool:
return ch.isalpha() or ch.isnumeric()
left_cursor = 0
right_cursor = len(s) - 1
same_count = 0
# 대상이 되는 문자열의 개수를 센다. (영숫자)
target_count = sum([1 for ch in s if is_alpha_or_number(ch)])
if target_count == 0:
return True
while left_cursor <= right_cursor:
# 영숫자가 아닌 경우, 커서를 이동시킨다.
while left_cursor <= right_cursor and not is_alpha_or_number(s[left_cursor]):
left_cursor += 1
while left_cursor <= right_cursor and not is_alpha_or_number(s[right_cursor]):
right_cursor -= 1
left_ch = s[left_cursor]
right_ch = s[right_cursor]
# 두 문자가 모두 영숫자인 경우, 대소문자를 무시하고 비교한다.
if is_alpha_or_number(left_ch) and is_alpha_or_number(right_ch):
if left_ch.lower() == right_ch.lower():
left_cursor += 1
right_cursor -= 1
same_count += 1
else:
return False
# 두 문자 중 하나라도 영숫자가 아닌 경우, 커서를 이동시킨다.
if not is_alpha_or_number(left_ch):
left_cursor += 1
if not is_alpha_or_number(right_ch):
right_cursor -= 1
# 대상이 되는 문자열의 개수의 절반만큼 같은 문자가 나왔는지 확인한다.
# 절반이 같아야 회문이다.
return same_count == (target_count // 2) + (target_count % 2)
Python
복사