[Python] 125. Valid Palindrome

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

Valid Palindrome - LeetCode

풀이

from collections import deque

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 소문자로 만들기
        s = s.lower()
        # 문자를 넣을 deque
        strings = deque()
        
        # 소문자로 통일한 문장에서 영어, 한글만 strings 덱에 추가
        for i in s:
            if i.isalnum() is True:
                strings.append(i)
        # 덱의 제일 앞과 뒤가 같은지 비교
        while len(strings) > 1: # 제일 앞과 뒤를 비교할 것이기 때문에 한개가 남으면 빠져나감
            if strings.popleft() != strings.pop():
                return False
        return True

---

팰린드롬

앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은말이 되는 단어

1. 공백제거
2. 알파벳 대소문자 통일
3. 비교

 

isalnum()

문자열이 영어, 한글 혹은 숫자로 되어 있으면 True 리턴

그렇지 않다면 False 리턴

print("python101".isalnum())

#True

 

lower()

소문자로 바꾼다.

* upper() : lower와 반대되는 함수

* islower() : 소문자인지 확인하는 함수

print("abcd".islower())

#True

---

시간을 단축시키기 위해

1.  리스트 말고 덱 이용하기

   리스트의 pop(0)는 O(n)인데 반해, 덱의 popleft()는 O(1)의 속도를 가짐.

   이를 n번씩 반복하면 리스트 구현은 O(n^2) 인데 반해, 덱의 구현은 O(n)로 성능차이가 큼.

2. 슬라이싱 이용하기

3. 처음에 모든 문자를 소문자로 바꾸는 것이 아닌 문자만 소문자로 바꾸도록 하기

4. len>= 2 보다 len > 1 사용하기

---

처음 생각했던 알고리즘의 문제점(틀린 이유)

1. 문자를 사용자한테 입력을 받는다 생각해서 input 함수를 넣었음
2. 공백 제거를 생각을 못함.

3. 한번 쓰는거면 애초에 선언을 안하는 것이 좋을 수도 있음 ex) bool 변수

 

그나마 잘한점

1. 슬라이싱 이용하려 했던 점...

bool = True
print("문자", s)
length = int(len(s)/2)
text = s.strip()
text = text.lower()
print("문자", s)
for i in range(length):
    if(text[i] != text[-i]):
        bool = False
return bool