Palindromic Substrings - LeetCode #647

문제 링크

Palindromic Substrings - LeetCode

풀이

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)  # 문자열의 길이를 구하기
        dp = [[False] * n for _ in range(n)]    # dp 리스트 초기화
        # dp[i][j]는 문자열 s[i:j+1]이 회문인지 여부를 저장
        count = 0

        # 길이가 1인 부분 문자열은 모두 회문
        for i in range(n):
            dp[i][i] = True
            count += 1

        # 문자열을 역순으로 순회하면서 각 문자를 확인
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                # 현재 문자와 다음 문자가 같다면
                if s[i] == s[j]:
                    # 인접한 경우: 두 문자로 이루어진 부분 문자열은 회문
                    if j - i == 1:
                        dp[i][j] = True
                    # 떨어져 있는 경우: 내부에 있는 문자열이 회문인지 확인
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                    if dp[i][j]:
                        count += 1

        return count