[leetcode 2024/02/05] 5.Longest Palindromic Substring

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법

 

처음에 해당 문제를 접근한 방법은 brute force를 이용한 방법이었다.

하지만 시간초과가 되어서 다른 접근 방법을 필요로 했다.

 

앞에서부터 접근하여, 같은 문자를 가지고 있을 떄, index 값들을 저장하고, 같은 문자 사이의 값들이 palindromic한지 알아보는 방법이다.

 

즉, bddb 라고 할 때, 앞에서 b를 char로 받는다. 이후, bddb에서 다른 b가 또 있는지 확인한다.

찾게 되면, 0 번째와 3번째 index의 값이 b 임을 알 수 있다. 

그랬을 때, 사이의 값들이 palindromic 한지 알아본다.

그 방법은 slice를 이용하였다.

s == s[::-1]

palindromic 인지 확인하였다.

 

이후 확인한 문자열은 searched list에 넣어서, 3 번째 index에 도달했을 때, 동일한 0 번째 index를 다시 search 할 필요 없도록 하였다.

 

2. 코드

class Solution:

    def Palindrome(self, s: str) -> bool:
        if (s == s[::-1]):
            return True
        else:
            return False

    def longestPalindrome(self, s: str) -> str:
        searched = []
        total = []
        for sub_str in s:
            if sub_str not in searched:
                searched.append(sub_str)
                indexes = [i for i, char in enumerate(s) if char == sub_str]

                for j in range(0,len(indexes),1):
                    k = j+1
                    while(k!=len(indexes)):
                        if(self.Palindrome(s[indexes[j]:(indexes[k]+1)])):
                            total.append(s[indexes[j]:indexes[k]+1])
                        k+=1
        total.sort(key=len, reverse=True)
        if not total:
            total.append(s[0])
        return total[0]

 

3. leetcode에서 제공해준 solution 코드

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

출처: tistory, [Leetcode] 5. Longest Palindromic Substring_ 해설, 풀이, 설명, https://hyunhp.tistory.com/409, 2024/02/05

 

나의 코드에서 더 발전할 수 있을 것 같아, 다른 코드들을 찾아보았다.

코드의 주된 내용은, for 문으로 중심을 잡은 후, 그 중심에서 왼쪽 그리고 오른쪽으로 뻗어나가는 것이다.

다음 문제, 15.Sum 문제처럼 2개의 pivot을 사용한다는 점이 특이적이다.

 

spread(i,i) 와 spread(i, i+1) 를 spread(i, j) 로 받는다.

i>=0 이고, j<n 이며, s[i] == s[j]를 만족할 때, 뻗어나간다.

이후, spread(i,i) 와 spread(i, i+1) 그리고 res(이전 for문의 i에서의 최대로 긴 문자열) 와 비교해서, 

가장 큰 값을 다시 저장한다.

 

여기서, spread(i,i)와 spread(i,i+1) 2가지를 하는 이유는

홀수 길이의 팰린드롬과, 짝수 길이의 팰린드롬 모두 고려해주기 위함이다.

 

++ 아주 신기하다. 뭔가 크게 깨달은 바가 있는 것 같다.