[Leetcode] 5. Longest Palindromic Substring_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '5. Longest Palindromic Substring'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Longest Palindromic Substring' 알고리즘 문제

 

STEP 2. 'Longest Palindromic Substring' 코드(code)

 

STEP 3. 'Longest Palindromic Substring' solution

 

반응형

 

STEP 1. 'Longest Palindromic Substring' 알고리즘 문제

 

Given a string s, return the longest palindromic substring in s.

문자열 s에서 가장 긴 반복 문자열을 구합니다.

(반복 문자열은 원래 문자열과 역으로 뒤집은 문자열이 동일한 것을 의미합니다)

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

 

---

STEP 2. 'Longest Palindromic Substring' 코드(code)

 

■ Runtime: 1147 ms, faster than 67.15% of Python3 online submissions for Longest Palindromic Substring.
■ Memory Usage: 14 MB, less than 68.98% of Python3 online submissions for Longest Palindromic Substring.

 

def longestPalindrome(self, s):
    res = ""
    for i in xrange(len(s)):
        # odd case, like "aba"
        tmp = self.helper(s, i, i)
        if len(tmp) > len(res):
            res = tmp
        # even case, like "abba"
        tmp = self.helper(s, i, i+1)
        if len(tmp) > len(res):
            res = tmp
    return res
 
# get the longest palindrome, l, r are the middle indexes   
# from inner to outer
def helper(self, s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1; r += 1
    return s[l+1:r]

 

 

STEP 3. 'Longest Palindromic Substring' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 776 ms, faster than 89.36% of Python3 online submissions for Longest Palindromic Substring.
■ Memory Usage: 14 MB, less than 32.60% of Python3 online submissions for Longest Palindromic Substring.

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
    
        n=len(s)
        res=0
        
        def spread(i,j):
            while i>=0 and j<n and s[i]==s[j]:
                i-=1
                j+=1
            return s[i+1:j]
        
        res=""
        for i in range(n):
            res=max(spread(i,i), spread(i,i+1),res, key=len)
        
        return res

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '5. Longest Palindromic Substring'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.