125. Valid Palindrome

문장이나 단어를 뒤집어도 동일한 것을 펠린드롬이라고 한다.
이번 문제는 대소문자 구별이 없고 알파벳과 숫자를 제외한 문자들이 펠린드롬을 충족하는지 검사하는 문제다.

Solution : 투 포인터

1. lower() 를 사용해 소문자로 변환한다.
2. isalnum() 을 사용해 알파벳 혹은 문자만 남긴다.
3. 투 포인터 를 사용해 순회하며 일치하는지를 검사한다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower() # 소문자 변환 # O(n)
        s = ''.join(c for c in s if c.isalnum()) # 알파벳과 숫자만 남기기 # O(n)
        start = 0
        end = len(s)-1
        while start < end: # O(n/2)
            if s[start] != s[end]: return False
            start += 1
            end -= 1
        return True

시간 복잡도 : O(n)

1번과 2번의 과정은 문자열의 길이에 비례하는 O(n) 시간 복잡도를 가진다.

3번의 경우에는 투 포인터를 사용해 양 끝에서부터 한 칸씩 이동하며 문자열을 비교한다. 이 방법을 사용하면 문자열의 길이의 절반 만큼만 순회하는 것으로도 해답을 구할 수 있기 때문에 시간 복잡도는 O(n/2) 이다.

O(n) + O(n) + O(n/2) 이므로 총 시간 복잡도는 O(n) 이다.

3번 과정은 투포인터를 사용하지 않고 문자열을 역순으로 만들어 원래의 문자열과 비교하는 방법도 가능하다.

rev_s = s[::-1] # 역순으로 만든다.
return s == rev_s

다만 위 방법의 시간 복잡도는 역순으로 만들 때에 O(n), 원래의 문자열과 비교할 때에 O(n)으로 O(2n)의 시간 복잡도를 가진다.

---

파이썬의 컴프리헨션을 잘 사용하고 싶다... ㅜㅜ
코드를 보면 알겠는데 직접 사용하려고 하면 감이 안 온다 흑