[LeetCode] 647. Palindromic Substrings

 

https://leetcode.com/problems/palindromic-substrings/description/?envType=problem-list-v2&envId=oizxjoit

Palindromic Substrings - LeetCode

 

Palindromic 문제는  center expansion으로 푸는 것이 정석이라고 한다.

## Center Expansion
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)

        def expand(l, r):
            cnt = 0
            while 0 <= l and r < n and s[l] == s[r]:
                cnt += 1
                l -= 1
                r += 1
            return cnt
        
        ans = 0
        for i in range(len(s)):
            ans += expand(i, i)
            ans += expand(i, i+1)
        return ans

 

이외에도 dynamic programming을 사용하는 방법도 있다고 한다.

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False]*n for _ in range(n)]
        ans = 0

        for r in range(n):
            for l in range(r, -1, -1):
                if s[l] == s[r] and (r - l <= 2 or dp[l+1][r-1]):
                    dp[l][r] = True
                    ans += 1
        return ans

 

dp의 역할은 각 index만 떼어서 봤을 때 palindrom인지를 의미하는 것

여기서 왜 (r - l <= 2)가 필요하냐?
dp[l+1][r-1] 는 안쪽 문자열을 보겠다는 뜻인데, 문자열 길이가 너무 짧으면 안쪽이 비거나(없거나) 한 글자가 되어버린다.

길이별로 보면
길이 1: "a" -> 항상 좌우 대칭
길이 2: "aa" -> 양 끝이 같으면 좌우 대칭, 안쪽은 “빈 문자열” (l+1 > r-1)
길이 3: "aba" -> 양 끝이 같으면 좌우 대칭, 안쪽은 길이 1 ("b") → 무조건 좌우 대칭

즉 길이가 1~3인 경우는 “안쪽 dp를 볼 필요 없이” 양 끝만 같으면 좌우 대칭이 확정된다.

정리하면 좌우 대칭 조건은
1. s[l] == s[r] 이고,
2. (r - l <= 2) (길이가 3 이하라 안쪽 확인 불필요)
3. 또는 dp[l+1][r-1] (길이가 4 이상이면 안쪽도 팰린드롬이어야 함)