문제 풀이/leetcode
[leetcode] valid palindrome
by akatapata
2022. 2. 16.
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
시간복잡도