[leetcode] valid palindrome

palindrome

• 앞으로 읽어도 뒤로 읽어도 동일

valid palindrome

• 대소문자를 구분하지 않고, Alphanumeric 아닌 문자는 제외
• 주어진 phrase 가 palindrome 인지 여부를 bool 로 리턴

대문자 <-> 소문자 변환

s = s.upper() # 대문자 변환 문자열 반환
s = s.lower() # 소문자 변환 문자열 반환

Alphanumeric만 추출하기

s = ''.join( c for c in s if c.isalnum())

# 정규표현식
import re
s = re.sub('\W','',s) # 문자열에서 \W(문자나 숫자가 아닌것)를 찾아서 제거한 문자열 반환

Solution

• start, end 두개의 index 를 이용 각각 앞, 뒤에서 Alphanumeric인 문자를 찾고 동일한지 비교를 반복
• 한번이라도 동일하지 않으면 False 리턴
• start < end 인 모든 경우에 동일하면 True

class Solution(object):
    def isPalindrome(self, s):
        start, end = 0, len(s)-1        

        while start < end:
            if not s[start].isalnum():
                start += 1
                continue
            if not s[end].isalnum():
                end -= 1
                continue
            if s[start].lower() != s[end].lower():
                return False
            start += 1
            end -= 1
        return True

시간복잡도

• O(n) : n=문자열 길이