Leetcode Python - 125. Valid Palindrome

Leetcode #125 - Valid Palindrome

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 125 ‘Valid Palindrome’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 two point를 시작과 끝을 기준으로 비교하며 만나는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def isPalindrome(self, s):
        string = s.lower()
        start = 0
        end = len(s)-1
        
        while start < end:
            while start<end and not string[start].isalnum():
                start += 1
            while start<end and not string[end].isalnum():
                end -= 1
            
            if string[start] != string[end]:
                return False
            else:
                start += 1
                end -= 1
        
        return True

시간복잡도는

• O(n) : 한 번의 while loop

공간복잡도는

• O(n) : s와 크기가 같은 string 생성