(*복습필요*) [LeetCode] Longest Palindromic Substring

leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

 

(0) 맨 처음에 내가 작성했던 코드

class Solution:
    
    def longestPalindrome(self, s: str) -> str:
        
        # palindrome substring 의 시작 index 0~(i-1)까지 쭉 해보기 !!
        l = len(s)
        longest_palindrome = ""
        
        # base case
        if (l <= 1):
            return s
        
        
        for start in range(l):
            for end in range(start+1, l+1): # O(n^2)... 성능최악일듯 ㅠㅠ --> 역시나...시간초과... ㅠㅠ
                my_str = s[start:end]
                if (len(longest_palindrome)< len(my_str)):
                    if self.is_palindrome(my_str):
                        longest_palindrome = my_str
        
        return longest_palindrome
    
    
    
    def is_palindrome(self, s: str) -> bool:
        d = collections.deque([v for v in s])
        while (len(d) > 1):
            if (d.pop() != d.popleft()):
                return False
        return True

흐엥.. 안그래도 O(n^2) 이라서 조마조마 했는데.... 역시나 ㅠㅠ 시간초과.....

 

(1) <파이썬 알고리즘 인터뷰> : 중앙을 중심으로 확장하는 풀이

class Solution:
    
    def longestPalindrome(self, s: str) -> str:
		# 팰린드롬 판별 및 투 포인터 확장
        def expand(left: int, right: int) -> str:
        	while left >=0 and right < len(s) and s[left] == s[right]:
            	left -= 1
            	right += 1
            return s[left+1 : right]
        
        # 해당 사항이 없을때 빠르게 리턴
        if len(s) < 2 or s==s[::-1]:
        	return s
        
        result = ''
        # 슬라이딩 윈도우 우측으로 이동
        for i in range(len(s)-1):
        	result = max(result,
            				expand(i, i+1),
                            expand(i, i+2),
                            key = len)
        
        return result
            

풀이를 읽어봤는데... 잘 모르겠다 ㅠ 이해가 안간다... 나중에 다시 읽어보거나, 다시 읽어봤는데도 이해안가면 구글링해서 다른 풀이들도 좀 찾아보고 그래야겠다... (p.159-162)

 

 

 

 

---

출처 :

책 <파이썬 알고리즘 인터뷰>