LeetCode 647: 팰린드롬 문자열 — 단계별 시각적 추적

Source: Dev.to

문제 설명

주어진 문자열에서 회문 부분 문자열의 총 개수를 세어라. 회문 부분 문자열은 앞뒤가 동일하게 읽힌다.

접근법

문자열의 모든 가능한 중심 위치를 확인하여 expand‑around‑centers 기법을 사용한다. 각 위치에서 양쪽 문자가 일치하는 동안 확장하여 홀수 및 짝수 길이의 회문을 셈한다.

복잡도

• 시간: O(n²)
• 공간: O(1)

솔루션

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expandAroundCenter(left: int, right: int) -> int:
            count = 0
            # Expand around the center while the characters at both ends are equal.
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                count += 1
            return count

        if not s:
            return 0

        total_palindromes = 0

        for i in range(len(s)):
            # Check for odd-length palindromes.
            total_palindromes += expandAroundCenter(i, i)

            # Check for even-length palindromes.
            total_palindromes += expandAroundCenter(i, i + 1)

        return total_palindromes