[LEETCODE] 125: Valid Palindrome(Python)

Valid Palindrome - LeetCode

문제 설명

주어진 문자열을 문자, 숫자만 남긴 후 소문자로 변경했을 때 그 문자열이 팰린드롬인지 확인하자.

나의 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        ns=''
        for i in s:
            if i.isalnum():
                ns+=i.lower()
        
        n=len(ns)
        for i in range(n//2):
            if ns[i]!=ns[n-i-1]:
                return False
        return True

내장 함수를 사용해 전처리를 진행하고 절반씩 나눠 비교했다.

시간복잡도

전처리 과정에서 O(n), 팰린드롬인지 비교하는 과정에서 O(n//2)가 걸린다. 즉 전체 시간복잡도는 O(n)이다.