Leetcode 5. Longest Palindromic Substring (Dynamic programming)

문제. 주어진 문자열 s에서 부분 문자열 중, 역순으로 읽어도 값이 같은 가장 긴 부분 문자열을 찾아서 반환하시오

 

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

Longest Palindromic Substring - LeetCode

 

---

첫 시도)

가장 첫 번째 아이디어는 어떤 과정으로 조건을 충족하는 부분문자열을 만들 수 있을까?였습니다.

그래서 고민을 통해 문자열의 길이가 홀수/짝수인지에 따라서 공통 문자열이 존재하는지 여부를 통해 값을 구할 수 있다고 생각해서 코드를 짰습니다

   while True:
            if len(s) %2 == 0:
                if s[len(s)/2] == s[(len(s)/2)-1]:
                    continue
                else:
                    s = s[:(len(s)/2)+1]
                    ...

하지만 중간에서부터 공통된 문자열을 찾고, 일치하지 않는 반을 슬라이싱 하여 진행하는 코드를 짜다보니 길을 잃었습니다..,,ㅜㅜ

 

---

 

재귀문 풀이 )

class Solution:
	def longestPalidrome(self,s:str) -> str:
    	p = ''
        for i in range(len(s)):
            p1 = self. get_palindrome(s,i,i+1)
            p2 = self.get_palindrome(s,i,i)
            p = max([p,p1,p2],key= lambda x: len(x))
          return p
          
  	def get_palindrome(self,s:str,l:int, r:int) -> str:
    	while l >= 0 and r < len(s) and s[l] == s[r]:
        	l -= 1
        	r += 1
        return s[l+1:r]

 

여기서  핵심 부분은 while 문을 통해 반복적으로 각 문자열을 중심으로 발생할 수 있는 부분 문자열을 뽑았는데요

while 0 <= i <= j <len(s) and s[i] == s[j]:

    i -= 1

    j += 1

return s[ i+1, j ]

while 문이 끝날때 즉, palindromic이 아닐때 반환되는 위치를 i + 1과 j 로 세팅했습니다

 

그리고 for 문을 통해서

b1 숫자가 짝수일 경우, b2 숫자가 홀수일 경우의 조합과 기존 max값과 비교해서 가장 큰 길이를 반환할때 값을 리턴하도록 합니다! 

 

Dynamic Programming )

 

def longestPalindrome(self, s):
        longest_palindrom = ''
        dp = [[0]*len(s) for _ in range(len(s))]
        #filling out the diagonal by 1
        for i in range(len(s)):
            dp[i][i] = True
            longest_palindrom = s[i]
			
        # filling the dp table
        for i in range(len(s)-1,-1,-1):
				# j starts from the i location : to only work on the upper side of the diagonal 
            for j in range(i+1,len(s)):  
                if s[i] == s[j]:  #if the chars mathces
                    # if len slicied sub_string is just one letter if the characters are equal, we can say they are palindomr dp[i][j] =True 
                    #if the slicied sub_string is longer than 1, then we should check if the inner string is also palindrom (check dp[i+1][j-1] is True)
                    if j-i ==1 or dp[i+1][j-1] is True:
                        dp[i][j] = True
                        # we also need to keep track of the maximum palindrom sequence 
                        if len(longest_palindrom) < len(s[i:j+1]):
                            longest_palindrom = s[i:j+1]
                
        return longest_palindrom

 

d이 풀이는 dynamic programming을 matrix의 관점에서 풀어낸 코드입니다.

 

대각선 (본인 자신이 palindrome)을 True로 세팅하고 나머지는 좌우로 좁혀오면서 palindrome 위주를 판별하고

palindrome 안에 palindrome이 있는 경우 True 를 주도록 했습니다.

 

 

 

 

 

Source: https://leetcode.com/problems/longest-palindromic-substring/discuss/900639/Python-Solution-%3A-with-detailed-explanation-%3A-using-DP

Python Solution : with detailed explanation : using DP - LeetCode Discuss

(혹시 실수가 있을 시 얼마든지 지적해주셔도 좋습니다!)