[leetcode] 125. Valid Palindrome 풀이, 해설 (python)

 

문제 링크

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

Valid Palindrome - LeetCode

 

neetcode 상에서 two pointers로 분류되어 있는 문제이다. 

 

1차 풀이

문제를 잘 읽어보면, removing all non-alphanumeric characters 라는 말이 보인다. 

알파벳이 아닌 문자들을 걸러줘야 한다. 이 부분은 isalnum 함수를 통해서 해결했다. 

참고로, isalnum 은 알파벳과 숫자를 허용하고, isalpha는 알파벳만 허용하는데, 문제 상에서는 알파벳과 숫자를 허용하기 때문에 isalnum을 사용해야 했다. 

- isalnum : https://zetawiki.com/wiki/%ED%8C%8C%EC%9D%B4%EC%8D%AC_isalnum()

- isalpha : https://zetawiki.com/wiki/%ED%8C%8C%EC%9D%B4%EC%8D%AC_isalpha()

class Solution(object):
    def isPalindrome(self, s):
        
        testString = [] 
        for c in s:
            if c.isalnum():
                testString.append(c.lower())
        
        for i,c in enumerate(testString):
            if c != testString[-i-1]:
                return False
        
        return True

 

 

2차 풀이 (해설 참고)

https://www.youtube.com/watch?v=jJXJ16kPFWg

첫번째로 해설강좌에서 제공해주는 방법은 다음과 같다. 

내 첫번째 풀이와 유사하지만, array 대신 스트링으로 해결하는 방법이다. 

조금 관심있게 볼만한 부분은 newStr == newStr[::-1] 통해서 array 배열 값 검사를 한 것.  파이썬에서는 array 자체를 비교가능하다. 

 newStr = "" 
    for c in s:
        if c.isalnum():
            newStr += c.lower()
    return newStr == newStr[::-1]

 

다음으로 제공해주는 방법은 추가적인 메모리 공간을 사용하지 않고 푸는 알고리즘 방법이다. 

while문 안에 while 문을 쓰는 뭔가 일할때 쓰면 안돼는 방식이라, 알고리즘이더라도 손이 안간다. 

하지만, 내가 제출했던 풀이 중에서, 메모리가 가장 적게 쓰이는 것을 확인할 수 있다. 

  l, r = 0, len(s) -1
        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1
            while r > l and not self.alphaNum(s[r]):
                r -= 1 
            
            if s[l].lower() != s[r].lower():
                return False      
            
            l, r = l + 1, r - 1
        
        return True
    
    
    def alphaNum(self, c):
        return (
            ord('A') <= ord(c) <= ord('Z') or
            ord('a') <= ord(c) <= ord('z') or
            ord('0') <= ord(c) <= ord('9') 
        )