5. Longest Palindromic Substring ★

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]은 팰린드롬의 성질을 정확히 반영한 조건입니다.

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