1216. Valid Palindrome III (String, Dynamic Programming)

링크 - https://leetcode.com/problems/valid-palindrome-iii/description/?envType=company&envId=facebook&favoriteSlug=facebook-three-months

난이도 - Hard

Intuition

1) Bottom-Up DP (2D)

우리는 2D list DP를 사용해 이 문제를 풀 수 있다. 알고리즘은 다음과 같다.

1. 먼저 DP를 nxn 리스트로 만든 뒤, 0으로 초기화 한다.

2. i는 n-2부터 0까지, j는 i+1부터 n-1까지 돌린다.

3. s[i] == s[j]이면, 우리는 그 사이의 dp값을 그대로 쓰면 되므로 dp[i][j] = dp[i+1][j-1]이 된다.

4. s[i] != s[j]이면, 우리는 그 사이의 dp값에서 하나를 제거해야 한다. 따라서 dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])이 된다. min을 써야 최소값을 계속 추적할 수 있다.

5. 마지막까지 오면 우리가 최종적으로 바꿔야 할 최소값은 dp[0][n-1]이다. 따라서 이 값이 k보다 작거나 같은지 확인한다.

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])

        return dp[0][n-1] <= k

Time Complexity: O(N^2)

Space Complexity: O(N^2)

2) Bottom-Up DP (1D)

위의 알고리즘에서 보면 우리는 항상 dp에서 i+1과 j-1를 참고하는 것을 알 수 있다. 따라서 우리는 space complexity를 O(n)으로 바꿀 수 있다.

우리는 각 i마다 prev를 통해 이전 결과값을 저장할 수 있다. 그리고 각 j마다 현재 dp[j]를 저장하고, dp[j]를 업데이트 한 다음, prev를 이전 dp[j]값으로 가져가는 식이다.

예를 들어보자. 우리가 abceca라는 글자의 최소 제거 값을 알고 싶다고 하자. 알고리즘은 다음과 같을 것이다.

(a - 0, b - 1, c - 2, e - 3, c - 4, a - 5)

1. 먼저 ca이다. (i=4, j=5) 우리는 dp[j=5]값을 구해야 하는데 c와 a가 같지 않으므로 min(dp[5], dp[4])값에 1를 더해야 한다. 따라서 dp[5] = 1이 된다.

2. 그 다음으로 eca이다. 우리는 dp[j=4]와 dp[j=5]값을 구해야 하는데 ec와 eca둘다 양쪽 끝 글자가 같지 않다. 먼저 ec는 당연히 dp[4] = 1이 될것이다. 또한 다음으로 dp[5] = 1 + min(dp[5], dp[4]) = 1 + min(1, 1) = 2가 된다. 

3. 그 다음으로 ceca이다. 우리는 dp[j=3],dp[j=4],dp[j=5]를 구해야 하는데 먼저 dp[3] 은 위와 같은 방법으로 1이 된다. 그 전에 원래 값이었던 dp[3] = 0을 이전값으로 가지고 있는다. 그 다음 dp[4]는 양쪽 글자가 같으므로 이전에 가지고 있었던 0을 가져온다. 따라서 dp[4] = 0이 된다. 그러므로 dp[5] = 1 + min(dp[4], dp[5]) = 1 + min(0, 2) = 1이 된다.

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        dp = [0] * len(s)

        for i in range(len(s)-2, -1, -1):
            prev = 0
            for j in range(i+1, len(s)):
                temp = dp[j]

                if s[i] == s[j]:
                    dp[j] = prev
                else:
                    dp[j] = 1 + min(dp[j], dp[j-1])
                prev = temp
            print(dp)

        return dp[len(s) - 1] <= k

Time Complexity: O(N^2)

Space Complexity: O(N)