LeetCode Day 55 (Day 54 is rest day) Dynamic Programming (15/17)

Continuing to practice with subsequences questions with dp!

Question 1

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

The first thing that comes to mind is the double pointer solution, which has a complexity of O(n) and is acceptable. However, since we are practising dynamic programming, it is better to solve it along the lines of dynamic programming.

When determining the recursive formula, first consider the following two operations, organised as follows:

• if (s[i - 1] == t[j - 1])
  • A character found in t also appears in s
• if (s[i - 1] ! = t[j - 1])
  • Equivalent to t to remove the element and continue matching

if (s[i - 1] == t[j - 1]) then dp[i][j] = dp[i - 1][j - 1] + 1;, because an identical character is found, the length of the identical subsequence naturally has to be added to dp[i-1][j-1] by 1

if (s[i - 1] ! = t[j - 1]), this time is equivalent to t to delete elements, t if the current element t[j - 1] deleted, then the value of dp[i][j] is Look at s[i - 1] and t[j - 2] of the results of the comparison of that, that is: dp[i][j] = dp[i][j - 1];

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = dp[i][j-1]
        if dp[-1][-1] == len(s):
            return True
        return False

Question 2

115. Distinct Subsequences

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

• nums1[i] == nums2[j], and
• the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

This question can’t be done with double pointers, you have to use dynamic programming.

Recursive formula for: dp[i][j] = dp[i - 1][j].

From the recursive formula dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; and dp[i][j] = dp[i - 1][j]; you can see that dp[i][j] is derived from the top and the top-left, then dp[i][0] and dp[0][j] must be initialised.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n1, n2 = len(s), len(t)
        if n1 < n2:
            return 0
 
        dp = [0 for _ in range(n2 + 1)]
        dp[0] = 1
 
        for i in range(1, n1 + 1):
 
            prev = dp.copy()
            end = i if i < n2 else n2
            for j in range(1, end + 1):
                if s[i - 1] == t[j - 1]:
                    dp[j] = prev[j - 1] + prev[j]
                else:
                    dp[j] = prev[j]
        return dp[-1]