[항해99] Longest Palindrome Substring

소스코드

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

문제 코드- Longest Palindrome Substring

class Solution:  
    def longestPalindrome(self, s: str) -> str:  
        # base case 0 , 1개 -> 자기자신  
        if len(s) <= 1:  
            return s  
        else:  
            # recursive step  
            # 양쪽 끝이 같다면!  
            if s[0] == s[-1]:  
                return s[0] + self.longestPalindrome(s[1:-1]) + s[-1]  
            # 양쪽 끝이 다른 경우  
            else: # abcb 라면!  
                # abc를 recursive하게  
                a = self.longestPalindrome(s[:-1])  
                # bcb를 recursive하게  
                b = self.longestPalindrome(s[1:])  
                # recursive하게 한 것 중에서 긴 애를 리턴해!  
                return a if len(a) >= len(b) else b  


solution_instance = Solution()  
s = input()  
ans = solution_instance.longestPalindrome(s)  
print(ans)

문제 접근 방식

Recursive한 방식으로 접근해보면 어떨까! 라는 생각으로
제일 큰 덩어리에서
만약에 양쪽이 같다면 -> return 처음 글자 + 함수(양쪽 뗀거) + 마지막 글자
만약에 양쪽이 다르다면 -> return 함수(처음 글자만 뗀 것), 함수(마지막 글자 뗀 것) 중에서 긴 애를 리턴!

base Case는 길이가 0이랑 1인 경우에는 자기 자신을 리턴해서 "" 또는 자기자신을 리턴하도록 만들었음.

문제 상황

근데 양쪽 끝에서부터 판별하다보니까, 안쪽에서 펠린드롬이 아니면 리턴했을 때 펠린드롬이 성립하지 않는 문제가 있음

예를들어 'aabcaa'의 경우에는 aa 가 나와야하는데, "a ( a( bc )a) a" 이라서 'aabaa'가 나옴

질문 내용

어떤 로직을 고치면 recursive하게 문제를 해결할 수 있을까요?

* 추가 : 왼쪽과 오른쪽 포인터를 이용해서 안쪽에서부터 바깥으로 쌓아가는 알고리즘 밖에 방법이 없을까요..?

답변

겉에서부터 붙이는 알고리즘은 아마 쓰기 힘들 것..
로직이 안쪽부터 판별해야 해서, 바깥에서부터 판별하면 문제가 생길 것.