125. Valid Palindrome

haaaalin·2023년 8월 25일

알고리즘 코테

LeetCode

목록 보기

10/31

문제 링크: https://leetcode.com/problems/valid-palindrome/?envType=study-plan-v2&envId=top-interview-150

문제

입력

문자열 s

출력

문자열 s가 pailndorme인지 True/False 값 반환

palindrome
: 영숫자(문자와 숫자)가 아닌 문자 모두 제거 후, 모든 대소문자를 소문자로 변환했을 때, 앞뒤가 같은 경우

나의 풀이

접근

어차피 string을 char 배열로 변환하면서 영숫자가 아닌 문자를 제거하고, 소문자로 변환하는 것까지 한 번에 다 하자! 라는 생각으로 접근했다.

그렇다면, 앞뒤가 똑같은 지 검사만 남았다.

일단 길이가 2보다 작은 경우는 무조건 True를 반환하도록 미리 걸러냈다.

Two Pointers 알고리즘을 이용

left와 right에 각각 첫 index와 끝 index를 할당
left를 myStr의 길이의 반만큼 반복문 수행
- left와 right가 가리키는 글자가 같다면 right 값 - 1
- 다르다면 바로 return False
지금까지 return이 되지 않았다면 앞뒤가 모두 똑같은 것이므로 return True

구현 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:

        myStr = [char for char in s.lower() if char.isalnum()]
        n = len(myStr)
        right = n - 1
        if n < 2:
            return True
        for left in range(n // 2):
            if myStr[left] != myStr[right]:
                return False
            if myStr[left] == myStr[right]:
                right -= 1

        
        return True

결과

Time: O(n)

Space: O(n)

다른 풀이 1

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	s = [i for i in s.lower() if i.isalnum()]
    	return s == s[::-1]

내가 Two Pointer를 이용해 구현했던 것을 python 언어의 특징을 이용하면 저렇게 짧게 한 줄로 표현할 수가 있었다.

s == s[::-1] → s의 문자열을 뒤집어서 원래의 s와 비교하는 구문

물론 알고리즘을 공부하려면 위의 코드보다는 직접 Two Pointer를 구현하는 게 좋겠지만, 공간복잡도나 시간복잡도가 더 적게 나왔기 때문에 이 코드도 기록해놓겠다.

다른 풀이 2

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	i, j = 0, len(s) - 1
    	while i < j:
    		a, b = s[i].lower(), s[j].lower()
    		if a.isalnum() and b.isalnum():
    			if a != b: return False
    			else:
    				i, j = i + 1, j - 1
    				continue
    		i, j = i + (not a.isalnum()), j - (not b.isalnum())
    	return True