647. Palindromic Substrings (Two Pointers, String, Dynamic Programming)

링크 - https://leetcode.com/problems/palindromic-substrings/editorial/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Dynamic Programming

이 문제는 dp를 통해서 풀 수 있다.

예를 들어 abcdedcba라는 string이 주어졌다고 하자. 그러면 이 string이 palindromic임을 어떻게 알 수 있을까? 알고리즘을 다음과 같이 짜면 된다.

0. 먼저 dp를 string의 길이인 n x n 2차원 배열로 만든다. 모든 값은 False로 초기화를 한다.

1. 먼저 각 글자 1개는 palindromic이다. 따라서 dp[i][i]는 True이다.

2. 2개 이어진 글자가 없으므로 3개의 글자를 보자. ded는 palindromic이다. 사실 이것은 e자체가 dp에서 True임을 알고, 왼쪽 d와 오른쪽 d가 같은 글자 d임을 확인함으로써 알 수 있다. 다시 말해, dp[4][4] = True임을 통해 e 자체가 palindromic이고, s[3] == s[5]이므로 따라서 dp[3][5]를 True로 설정한다.

3. 다음은 5개의 글자를 보자. cdedc는 palindromic이다. 사실 이것은 ded가 dp에서 True임을 알고, 왼쪽 c와 오른쪽 c가 같은 글자 c임을 확인함으로써 알 수 있다. 다시 말해, dp[3][5] = True임을 통해 s[3:6]=ded가 palindromic이고, s[2] == s[6]이므로 dp[2][6]을 True로 설정한다.

4. 이 과정을 반복하면서 ans를 카운트한다.

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        if not s:
            return ans

        n = len(s)
        dp = [[False] * n for _ in range(n)]

        # Base case: single word
        for i in range(n):
            dp[i][i] = True
            ans += 1

        # Base case: two consequtive words
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                ans += 1

        # Remaining case: All other cases with length >= 3
        for l in range(2, n):
            for left in range(n - l):
                right = left + l
                if dp[left+1][right-1] and s[left] == s[right]:
                    dp[left][right] = True
                    ans += 1

        return ans

 

Time Complexity: O(n^2) 우리는 n(n-1)/2만큼의 계산이 필요하다.

Space Complexity: O(n^2) 우리는 n(n-1)/2만큼의 공간이 필요하다. 하지만 dp를 2차원 배열로 만들었으므로 사실은 n^2공간을 사용했다.

2) Expand Around Possible Centers

이 방식은 각각의 인덱스에서 palindromic한 글자를 확장하는 방식으로 찾는 방법이다. 

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0

        if not s:
            return ans

        for i in range(len(s)):
            # odd-length palindromes, single character center
            ans += self.validatePalindromic(s, i, i)
            # even-length palindromes, consecutive characters center
            ans += self.validatePalindromic(s, i, i+1)

        return ans

    def validatePalindromic(self, s, left, right):
        ans = 0

        while left >= 0 and right < len(s):
            if s[left] != s[right]:
                break

            ans += 1
            left -= 1
            right += 1

        return ans

Time Complexity: O(n^2) 우리는 n(n-1)/2만큼의 계산이 필요하다.

Space Complexity: O(1)