๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜/LEETCODE

Longest Palindromic Substring | LeetCode 780 | Python3 ๐Ÿ

๋ฐ˜์‘ํ˜•

 

๐Ÿ“„ ๋ชฉ์ฐจ

     

    ๐Ÿค” ๋ฌธ์ œ : Longest Palindromic Substring | LeetCode 780

    ๋ฌธ์ œ: https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/780/
    palindorme : ๊ฑฐ๊พธ๋กœ ์ฝ์–ด๋„ ์ œ๋Œ€๋กœ ์ฝ๋Š” ๊ฒƒ๊ณผ ๊ฐ™์€ ๋ฌธ์žฅ์ด๋‚˜ ๋‚ฑ๋ง, ์ˆซ์ž, ๋ฌธ์ž์—ด(sequence of characters) 

    ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์—์„œ ๊ฐ€์žฅ ๊ธด palindrome์„ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

    palindrome์€ ํ•ญ์ƒ ํ™€์ˆ˜ palindrome ์ง์ˆ˜ palindrome ๋‘๊ฐ€์ง€ ์ผ€์ด์Šค ๋ชจ๋‘ ๊ณ ๋ คํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.!

    ํ™€์ˆ˜ palindrome: babad

    ์ง์ˆ˜ palindrome: cbbd

     

    ๐Ÿ’ก ํ’€์ด

    1. ๋ฌธ์ž์—ด์„ ์ˆœํšŒํ•˜๋ฉฐ ํ•ด๋‹น ๋ฌธ์ž๋ฅผ ์ค‘๊ฐ„๋ฌธ์ž๋กœ ํ•˜๋Š” ๊ฐ€์žฅ ๊ธด palindrome ์ฐพ๊ธฐ

    ๊ฐ€์žฅ ์ฒ˜์Œ์œผ๋กœ ์ ‘๊ทผํ•œ ํ’€์ด์ž…๋‹ˆ๋‹ค. 

    ํŠน์ • ๋ฌธ์ž๋ฅผ ์ค‘์‹ฌ์œผ๋กœ ๊ฐ€์žฅ ๊ธด palindrome์„ ์ฐพ๋Š” getPalindrome์ด๋ผ๋Š” ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค์—ˆ๊ณ ,

    ์ฃผ์–ด์ง„ ๋ฌธ์ž์—ด์„ ์ˆœํšŒํ•˜๋ฉฐ palindrome์„ ํ˜ธ์ถœํ–ˆ์Šต๋‹ˆ๋‹ค.

     

    ๋ถ€๋ถ„๋ฌธ์ž์—ด(substring)์„ ๋‹ค๋ฃจ๋Š” ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค ๋•Œ๋Š”,

    ๋ฌธ์ž์—ด์„ ์ง์ ‘ ๋งŒ๋“ค์–ด์„œ ์ „๋‹ฌํ•˜๋Š” ๊ฒƒ ๋ณด๋‹ค index๋งŒ ์ฃผ๊ณ ๋ฐ›๋Š”๊ฒŒ ํ›จ์”ฌ ๋น ๋ฆ…๋‹ˆ๋‹ค.

     

    from typing import List
    class Solution:
        def longestPalindrome(self, s: str) -> str:
            str_length = len(s)
    
            def getPalindrome(idx1, idx2):
                if idx1 < 0: return (idx1, idx2)
                if idx2 >= str_length: return (idx1, idx2)
                if s[idx1] is not s[idx2]: return (idx1, idx2)
                return getPalindrome(idx1-1, idx2+1)
    
            longest_palindrome_size = 0
            longest_palindrome_pair = None
            for idx in range(str_length):		# [1] 
                (st, ed) = getPalindrome(idx, idx) # [2]
                if ed-st-1 > longest_palindrome_size:
                    longest_palindrome_pair = (st, ed)
                    longest_palindrome_size = ed-st-1
    
                (st, ed) = getPalindrome(idx, idx+1) # [3]
                if ed-st-1 > longest_palindrome_size:
                    longest_palindrome_pair = (st, ed)
                    longest_palindrome_size = ed-st-1
    
            return s[longest_palindrome_pair[0]+1:longest_palindrome_pair[1]]

    [1]  idx๋ฒˆ์งธ ๋ฌธ์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ palindrome์„ ์ฐพ์„ ๊ฒƒ 

    [2] ํ™€์ˆ˜ palindrome  ex) cabad

    [3] ์ง์ˆ˜ palindrome ex) cabbad

     

    Time Complexity
    ๋ฌธ์ž์—ด์˜ ๊ฐ character์— ๋Œ€ํ•ด(n) palindrome์ธ์ง€ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๋ฏ€๋กœ (n)
    O(n^2) ์ž…๋‹ˆ๋‹ค. 

    Space Complexity
    ๋ณ„๋„ ๊ณต๊ฐ„์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

     

     

     

    2. 1์˜ ํ’€์ด๋ฅผ ๋ฌธ์ž์—ด์„ ๋งŒ๋“œ๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•œ ๊ฒฝ์šฐ

    ๋ฌธ์ž์—ด์„ ๋งŒ๋“ค์–ด ์ „๋‹ฌํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•œ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.

    Runtime์ด 5077ms์œผ๋กœ 5๋ฐฐ๊ฐ€๋Ÿ‰ ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋„ค์š”.

    class Solution:
        def longestPalindrome(self, s: str) -> str:
            str_length = len(s)
    
            def palindrome(idx1, idx2, curr_str):
                if idx1 is idx2: return palindrome(idx1-1, idx2+1, curr_str+s[idx1])
                if idx1 < 0: return curr_str
                if idx2 >= str_length: return curr_str
                if s[idx1] is not s[idx2]: return curr_str
                return palindrome(idx1-1, idx2+1, s[idx1]+curr_str+s[idx2])
    
            longest_palindrome = ""
            for idx in range(str_length):
                new_palindrome = palindrome(idx, idx, "")
                longest_palindrome = new_palindrome if len(longest_palindrome) <  len(new_palindrome) else longest_palindrome
                new_palindrome = palindrome(idx, idx+1, "")
                longest_palindrome = new_palindrome if len(longest_palindrome) <  len(new_palindrome) else longest_palindrome
            return longest_palindrome

     

    3. dynamic programming

    ๋‘ ์ธ๋ฑ์Šค ์‚ฌ์ด์˜ substring์ด palindrome์ธ์ง€ ์—ฌ๋ถ€๋ฅผ 2์ฐจ์› ๋ฐฐ์—ด(cache)์— ๋”ฐ๋กœ ์ €์žฅํ•ด๋‘๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

    dabac ์˜ ๊ฒฝ์šฐ cache๋ชจ์Šต์ด ์•„๋ž˜์™€ ๊ฐ™๊ฒ ๋„ค์š”.

      d a b a c
    d 1 0 0 0 0
    a   1 0 1 0
    b     1 0 0
    a       1 0
    c         1

    cache์˜ ๊ฐ’์„ ์ฑ„์šฐ๋Š” ๋กœ์ง์€ ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

    • ๋Œ€๊ฐ์„  ์š”์†Œ๋Š” ๋ชจ๋‘ 1 
    • ๋Œ€๊ฐ์„  ์™ผ์ชฝ ์•„๋ž˜ ์š”์†Œ๊ฐ€1์ด๊ณ  (์‹œ์ž‘, ๋ ๋ฌธ์ž์—ด ์ œ์™ธ palindrome)
      ํ˜„์žฌ ๊ฐ€๋กœ์ถ•๊ณผ ์„ธ๋กœ์ถ•์˜ ๋ฌธ์ž๊ฐ€ ๊ฐ™๋‹ค๋ฉด ์‹œ์ž‘, ๋ ๋ฌธ์ž๊ฐ€ ๊ฐ™์Œ) 1 
    • ๋‚˜๋จธ์ง€๋Š” 0
        def longestPalindrome(self, s: str) -> str:
            n = len(s)
            if n is 1: return s
        
            cache = [[0] * n for _ in range(n)]
            maxLength = 1
            longest_index_pair = (0,0)
        
            for i in range(n):
                cache[i][i] = 1
        
            for i in range(n-1):
                if s[i] is s[i+1]:
                    if maxLength < 2:
                        maxLength = 2
                        longest_index_pair = (i, i+1)
                    cache[i][i+1] = 1
        
            for i in range(2, n):
                for j in range(n-i):
                    x = j
                    y = j+i
        
                    if s[x] is s[y] and cache[x+1][y-1]:
                        cache[x][y] = 1
                        if maxLength < i+1:
                            maxLength = i+1
                            longest_index_pair = (x, y)
            return s[longest_index_pair[0]:longest_index_pair[1]+1]

     

     

    Time Complexity
    O(N^2)

    Space Complexity 
    O(N^2)

     

    Time Complexity๊ฐ€ ๋˜‘๊ฐ™์ด N^2์ธ 1๋ฒˆ ํ’€์ด์— ๋น„ํ•ด ์ˆ˜ํ–‰์‹œ๊ฐ„์ด ํ›จ์”ฌ ์˜ค๋ž˜๊ฑธ๋ฆฌ๋„ค์š”.

    ์•„๋ฌด๋ž˜๋„ ์ค‘๊ฐ„์— palindrome์ด ์•„๋‹Œ๊ฒŒ ํ™•์‹คํ•œ ์ผ€์ด์Šค๋ผ๋„ ์ „์ฒด๋ฅผ ๋‹ค ๋ณด๊ธฐ ๋•Œ๋ฌธ์ธ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

    1์€ worst case๊ฐ€ N^2์ด์˜€๋‹ค๋ฉด, ์ด ํ’€์ด๋Š” ๋ฌด์กฐ๊ฑด N^2์ธ ๊ฑฐ์ฃ 

     

     

    4. ๋” ๋น ๋ฅด๊ฒŒ - ์—ฐ์†๋œ ๋ฌธ์ž์—ด์ด ๋‚˜์˜ฌ ๊ฒฝ์šฐ palindromeํ™•์ธ ์—†์ด skip

    ๋‹ค๋ฅธ ํ’€์ด๊ฐ€ ์žˆ์„๊นŒ discussion์„ ๋ณด๋‹ค๊ฐ€ ์•Œ๊ฒŒ๋œ ํ’€์ด์ธ๋ฐ, ๊ฐ„๋‹จํ•˜๊ณ  ์ฐธ์‹ ํ•˜์—ฌ ๊ฐ™์ด ์†Œ๊ฐœํ•ฉ๋‹ˆ๋‹ค.

     

    ์ด ํ’€์ด๋Š” ๊ฐ™์€ ๋ฌธ์ž๊ฐ€ ์—ฐ์†ํ•ด์„œ ๋‚˜์˜ฌ ๊ฒฝ์šฐ์—๋Š” ๋‹ค ์Šคํ‚ตํ•˜๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

    ์ƒ๊ฐํ•ด๋ณด๋ฉด, ๊ฐ™์€ ๋ฌธ์ž๊ฐ€ ์—ฐ์†ํ•ด์„œ ๋‚˜์˜จ๋‹ค๋ฉด ์ขŒ์šฐ๋ฅผ 1:1๋กœ ๊ตณ์ด ๋น„๊ตํ•  ํ•„์š”๊ฐ€ ์—†๊ฒ ์ฃ .

    worst case(๊ฐ™์€ ๋ฌธ์ž๊ฐ€ ์—ฐ์†ํ•ด์„œ ๋‚˜์˜ค์ง€ ์•Š๋Š” ๊ฒฝ์šฐ)๋Š” N^2์œผ๋กœ ๊ฐ™๊ฒ ์ง€๋งŒ, ํ‰๊ท  ์ˆ˜ํ–‰์†๋„๋Š” ๋นจ๋ผ์ง€๊ฒ ๋„ค์š”.

        # expand same characters
        def longestPalindrome(self, s: str) -> str:
            """
            The longest Palindrome including s[i] should contains substr s[l+1, r],
    		where all elements in s[l+1, r] are s[i]
    		This saves checks when a same char is repeated consecutively in s.
    		"""
            p, idx = '', 0
            while idx < len(s):
    			l = r = idx
    			# expand when having same ajacent chars
    			while l-1>=0 and s[l] == s[l-1]: l -= 1
    			while r+1<len(s) and s[r] == s[r+1]: r+=1
    			idx = r+1 # update idx, this can save checks
        
    			# expand to different chars
    			while l>=0 and r<len(s) and s[l] == s[r]:
    				l, r = l-1, r+1
    			# update p
    			p = max([p, s[l+1:r]], key = lambda x:len(x))
        
    		return p

     

    ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์— ์—ฐ์†๋œ ๋ฌธ์ž์—ด์ด ๋งŽ์•˜๋Š”์ง€ ์ˆ˜ํ–‰์†๋„๊ฐ€ ๊ฑฐ์˜ 1/10์œผ๋กœ ์ค„์—ˆ๋„ค์š”!

    palindrome์ด ์ขŒ์šฐ ๋Œ€์นญ์ด๋ผ๋Š” ์ƒ๊ฐ์—๋งŒ ๊ฐ‡ํ˜€ ์ด๋Ÿฐ ์ฐธ์‹ ํ•œ ์ƒ๊ฐ์„ ๋– ์˜ฌ๋ฆฌ์ง€ ๋ชปํ–ˆ๋˜๊ฒŒ ์•„์‰ฝ์Šต๋‹ˆ๋‹ค. ใ…œใ…œ 

     

    ๋ฐ˜์‘ํ˜•