LeetCode Day 57 Dynamic Programming (17/17)

Today is the last day of the Dynamic Programming exercise!

Question 1

647. Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

It can be solved with Brute force, but it requires two layers of for loops to traverse the interval start position and end position, and then one more layer of traversal to determine if the interval is a palindrome. So the time complexity is O(n^3).

So we also have to use dynamic programming. When determining the recursive formula, the following cases have to be analysed.

Overall there are two kinds, that is, s[i] and s[j] are equal and s[i] and s[j] are not equal these two kinds.

When s[i] is not equal to s[j], there’s nothing more to say, dp[i][j] must be false.

When s[i] is equal to s[j], this is a bit more complicated, with the following three cases

1. Case 1: subscripts i and j are the same, the same character e.g. a, which is of course a palindrome substring
2. Case 2: the difference between subscript i and j is 1, such as aa, which is also a palindrome.
3. Case 3: subscript: i and j difference is greater than 1, such as cabac, at this time s[i] and s[j] has been the same, we look at the i to j interval is not a palindrome sub-string on the aba is not a palindrome on it, then aba’s interval is the interval of i +1 and j-1 interval, the interval is not a palindrome on the look at the dp[i + 1][j - 1] whether or not it is true.

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1): 
            for j in range(i, len(s)):
                if s[i] == s[j] and (j - i <= 1 or dp[i+1][j-1]): 
                    result += 1
                    dp[i][j] = True
        return result

Question 2

516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Still applying the five parts of dynamic programming:

1. Determine the dp array (dp table) and the meaning of the subscripts
   1. dp[i][j]: the length of the longest echo subsequence of string s in the range [i, j] is dp[i][j].
2. Determining the recursive formula
   1. In the topic of determining palindromic substrings, the key logic is to see if s[i] is the same as s[j]. If s[i] is the same as s[j], then dp[i][j] = dp[i + 1][j - 1] + 2;
   2. If s[i] and s[j] are not the same, it means that the simultaneous addition of s[i] and s[j] can not increase the length of the echo subsequence in the interval [i,j], then add s[i] and s[j] separately to see which one can form the longest echo subsequence.
   3. The length of the echo subsequence joining s[j] is dp[i + 1][j].
   4. The length of the palindrome subsequence joining s[i] is dp[i][j - 1].
   5. Then dp[i][j] must be taken as the maximum, i.e., dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
3. How the dp array is initialised
   1. First of all, we need to consider the case when i and j are the same, from the recursive formula: dp[i][j] = dp[i + 1][j - 1] + 2; we can see that the recursive formula can not calculate the case when i and j are the same.
   2. So we need to initialise it manually, when i and j are the same, then dp[i][j] must be equal to 1, i.e.: the length of the echo subsequence of a character is 1.
   3. Other cases dp[i][j] initial 0 on the line, so that the recursive formula: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); in dp[i][j] will not be covered by the initial value.
4. Determining the traversal order
   1. From the recursive formula, we can see that dp[i][j] depends on dp[i + 1][j - 1], dp[i + 1][j] and dp[i][j - 1]. So traversing i must be done from bottom to top to ensure that the data in the next row is computed.
5. Example derivation of dp array

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s)-1, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][-1]