05_Longest_Palindromic_Substring (작성중)

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

역시나 못 풀었던 문제였다. 로직은 짰는데 사실상 brute-force식이었는데 그마저도 어떻게 구현해야할지 감이 도저히 안 와서 좌절했었는데, 원체 어려운 문제였다. 왜냐하면 dynamic programming(DP) 관련 문제였기 때문. 하지만 뭔가 굉장히 많이 배운 문제였는데, 솔루션이 다양해 분석하는 맛이 있었기 때문이었다. 코드가 어떻게 굴러가는지에 대해서도 잘못알고 있던 게 있어서 배운 게 많았음. 아래 솔루션들은 가장 많은 호응을 받은 포스트에서 긁어온 거다.

솔루션 1: Brute force

아이디어(혹은 직관)
→ 시작점과 끝지점을 모두 하나하나 체크하면서 substring이 회문인지 아닌지 체크

• 알고리즘

1. 리스트로 구성된 substring의 시작 인덱스를 선택하며, 이는 0부터 n-2까지의 모든 인덱스다.
2. 마찬가지로 리스트로 구성된 substring의 마지막 인덱스를선택하며, 이는 i+1부터 n-1까지의 인덱스다.
3. i번째 인덱스부터 j번째까지의 substring이 회문인지 확인한다.
4. 3번 단계에서 참을 얻고 해당 substring의 길이가 기존 설정한 길이보다 길다면, 최대 길이 변수와 최대 길이 substring을 업데이트한다.
5. 최대 길이(=가장 긴 or longest) substring을 출력한다.

• 구현

class Solution:
	def longestPalindrome(self, s: str) -> str:
    	if len(s) <= 1: # 회문 자체를 얻어낼 수 없는 경우엔 s로 리턴. 길이가 1보다 작거나 같으면 회문이 안됨.
        	return s
        
        Max_Len = 1
        Max_Str = s[0]
        for i in range(len(s)-1): # step 1 cf. (range(n)) = (0, n-1)	
        	for j in range(i+1, len(s)): # step 2 cf. (range(x, y)) = ((x, y-1))
            	if j-1+1 > Max_Len and s[i:j+1] == s[i:j+1][::-1]: # step 3
                	Max_Len = j-i+1
                    Max_Str = s[i:j+1]
                    
        return Max_Str

솔루션 2: Expand around center

아이디어(혹은 직관)
→ Two-pointer가 있고 얘네들이 string의 중앙을 중심으로 확장하는 방식.

• 접근법

1. 회문은 기본적으로 중앙을 중심으로 양쪽의 문자들이 거울처럼 바라보는 것임. 따라서 회문은 중앙에서부터 확장되며, 그러한 중앙의 갯수는 2n-1개.
2. 왜 2n-1개인가? 그냥 n개의 중앙이 아니라? 왜냐하면 회문의 중심이 두 개의 문자 사이에 있을 수 있기 때문임. 그런 회문은 짝수 갯수의 문자를 갖고 있고 (ex. "abba") 그 중심은 두 개의 'b' 사이인 경우임.

• 알고리즘

1. 시작점에서 max_str = s[0], max_len = 1로 설정하는데 원론적으로 모든 개개의 문자 그 자체는 회문이기 때문임.
2. 주어진 스트링에 대해서 계속 반복적으로 처리하면서 모든 문자에 대해서 중앙을 중심으로 확장함.
3. 홀수 길이의 회문에 대해선 현재 포인팅이 된 문자를 중앙으로 간주하고 이를 중심으로 확장.
4. 짝수 길이의 회문에 대해선 현재 포인팅이 된 문자와 그 다음 문자를 중앙으로 간주하고 이를 중심으로 확장.
5. 그러면서 최대 길이와 최대 길이의 substring 추적.
6. 가장 긴 회문을 찾으면 출력함.

• 구현

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        def expand_from_center(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]

        max_str = s[0]

        for i in range(len(s) - 1):
            odd = expand_from_center(i, i)
            even = expand_from_center(i, i + 1)

            if len(odd) > len(max_str):
                max_str = odd
            if len(even) > len(max_str):
                max_str = even

        return max_str

솔루션 3: Dynamic Programming
아이디어(혹은 직관)
→ 일종의 Table을 만들어서 그 안에서 계산하면서 True가 뜰 때 마다 회문인 걸 확인하고선 저장하는 방식..위에 두 개도 좋긴한데 이게 나한텐 더 직관적임.

• 알고리즘
  (작성중)
• 구현

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s
        
        Max_Len=1
        Max_Str=s[0]
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = True
            for j in range(i):
                if s[j] == s[i] and (i-j <= 2 or dp[j+1][i-1]):
                    dp[j][i] = True
                    if i-j+1 > Max_Len:
                        Max_Len = i-j+1
                        Max_Str = s[j:i+1]
        return Max_Str

끝.