LeetCode/DP심화

5. Longest Palindromic Substring ★

hyunkookim 2024. 12. 30. 20:01

5. Longest Palindromic Substring

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s  # 문자열 길이가 1일 경우, 해당 문자열 반환
        
        res = ""  # 가장 긴 팰린드롬 문자열을 저장할 변수
        
        for ln in range(1, len(s) + 1):  # 부분 문자열 길이 탐색
            for i in range(len(s) - ln + 1):  # 시작 인덱스 탐색
                substring = s[i:i + ln]  # 부분 문자열 추출
                # 팰린드롬 확인 및 길이가 기존 결과보다 긴 경우 업데이트
                if substring == substring[::-1] and len(substring) > len(res):
                    res = substring
        
        return res  # 가장 긴 팰린드롬 반환

 

단, 시간은 오래 걸림

 

최종 개선 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:    	
		"""
        # 임의의 단어가 중심 단어라고 생각하고
        # n 만큼 좌우 길이를 확장하며 팰린드롬을 확인
        """
        res = ""
        resLen = 0

        for i in range(len(s)):
            # 홀수 길이 팰린드롬
            l, r = i, i
            while 0 <= l and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l:r + 1]
                    resLen = r - l + 1
                l -= 1
                r += 1

            # 짝수 길이 팰린드롬
            l, r = i, i + 1
            while 0 <= l and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l:r + 1]
                    resLen = r - l + 1
                l -= 1
                r += 1

        return res  # 모든 중심을 확인한 후 결과 반환

 

동작 원리

  1. 홀수 길이 팰린드롬:
    • 현재 문자(i)를 중심으로 좌우로 확장하며 팰린드롬인지 확인합니다.
  2. 짝수 길이 팰린드롬:
    • 현재 문자(i)와 그 다음 문자(i+1)를 중심으로 좌우로 확장하며 팰린드롬인지 확인합니다.
  3. 최대 길이 업데이트:
    • 확장한 팰린드롬의 길이가 현재 저장된 결과보다 길면 결과를 갱신합니다.
  4. 최종 결과 반환:
    • 모든 문자에 대해 중심을 확인한 후 가장 긴 팰린드롬을 반환합니다.

시간 및 공간 복잡도

  1. 시간 복잡도: O(n2)
    • 모든 문자를 중심으로 확장하며, 각 확장은 최대 n번 수행됩니다.
  2. 공간 복잡도: O(1)
    • 추가 메모리를 거의 사용하지 않습니다.

 

공통 코드 부분

while 0 <= l and r < len(s) and s[l] == s[r]:
    if (r-l+1) > resLen:
        res = s[l:r+1]
        resLen = r-l+1
    l -= 1
    r +=1

 

이 코드의 동작

  1. 조건 확인:
    • 0 <= l 및 r < len(s):
      • 팰린드롬의 확장이 문자열 범위를 벗어나지 않도록 합니다.
    • s[l] == s[r]:
      • 현재 양 끝의 문자가 동일한 경우에만 확장을 계속합니다.
  2. 현재 팰린드롬 길이 확인:
    • (r - l + 1)은 현재 팰린드롬의 길이입니다.
    • 현재 팰린드롬 길이가 resLen보다 크면, res와 resLen을 갱신합니다.
  3. 범위 확장:
    • l -= 1: 왼쪽으로 확장.
    • r += 1: 오른쪽으로 확장.

이 부분의 역할

  • 이 코드는 현재 중심에서 가능한 가장 긴 팰린드롬을 찾는 역할을 합니다.
  • 중심이 되는 문자에서 좌우로 확장하며 조건이 만족되는 동안 계속 확장합니다.

동일한 부분이 두 번 있는 이유

  1. 홀수 길이 팰린드롬:
    • 중심이 하나의 문자일 때, 즉 팰린드롬이 홀수 길이를 가지는 경우를 처리합니다.
  2. 짝수 길이 팰린드롬:
    • 중심이 두 개의 문자일 때, 즉 팰린드롬이 짝수 길이를 가지는 경우를 처리합니다.

짝수와 홀수의 중심 처리를 위해 동일한 코드가 두 번 사용됩니다.

 

if 문에서 s[l] == s[r] 는 끝단어만 확인하는데, 왜 가능하지??

=> 다르면, 중간에서 다르면, 이미 l, r 이 증가함.. 

 
자세히 살펴보면 ..

 

코드의 s[l] == s[r]는 현재 확장 과정에서 양 끝 문자가 같은지 확인하는 조건입니다. 이 조건은 팰린드롬을 찾기 위해 반드시 필요하며, 전체 팰린드롬 문자열을 정확히 확인하는 방식으로 작동합니다.


왜 s[l] == s[r]로 충분한가?

팰린드롬은 양 끝에서 가운데로 대칭인 문자열입니다.

따라서 팰린드롬인지 확인하려면, 현재 확인 중인 양 끝 문자(s[l]와 s[r])가 같아야 합니다.

이 조건을 만족하는 동안, 양 끝에서 안쪽으로 계속 확인하며 팰린드롬을 확장하게 됩니다.

예제 1: "aba"

  1. l=0,r=2 → s[l] == s[r] → 'a' == 'a'
    • 계속 확장: l=−1,r=3 → 종료.
  2. "aba"는 팰린드롬으로 확인됩니다.

예제 2: "abba"

  1. l=0,r=3 → s[l] == s[r] → 'a' == 'a'
    • 계속 확장: l=1,r=2 → s[l] == s[r] → 'b' == 'b'
    • 계속 확장: l=0,r=4 → 종료.
  2. "abba"는 팰린드롬으로 확인됩니다.

전체 문자열을 확인하는 이유

while 루프가 확장하며 반복적으로 양 끝 문자를 비교하므로, 전체 문자열을 정확히 확인합니다.

팰린드롬이 아닌 경우 조건을 만족하지 못해 즉시 중단됩니다.

예제 3: "abc"

  1. l=0,r=2 → s[l] != s[r] → 'a' != 'c'
    • 루프 중단, 팰린드롬 아님.

잘못 찾는 경우는 발생하지 않는 이유

  1. s[l] == s[r] 조건은 항상 양 끝이 같은 경우에만 확장을 수행하므로, 잘못된 부분 문자열이 팰린드롬으로 확인되는 일은 없습니다.
  2. 팰린드롬이 아닌 경우 즉시 중단되므로, 잘못된 결과를 반환하지 않습니다.

결론

while s[l] == s[r]은 팰린드롬의 성질을 정확히 반영한 조건입니다.

잘못 찾는 경우는 발생하지 않습니다. 양 끝에서 시작해 점점 안쪽으로 확장하기 때문에, 이 조건만으로도 정확히 팰린드롬을 확인할 수 있습니다.

'LeetCode > DP심화' 카테고리의 다른 글

188. Best Time to Buy and Sell Stock IV  (2) 2024.12.31
123. Best Time to Buy and Sell Stock III ★★★  (0) 2024.12.31
64. Minimum Path Sum  (0) 2024.12.30
120. Triangle  (0) 2024.12.30
300. Longest Increasing Subsequence ★  (0) 2024.12.29