I have solved solution 392 on LeetCode and one of the topics listed for it is Dynamic Programming. Looking at my code and other solutions online, I wonder what part of the solution is categorized as pertaining to Dynamic Programming. I would appreciate it if someone could enlighten me and help me have a better understanding of this.

The solution explanation is paywalled for me on LeetCode as I don't have premium, so I am trying to open source this understanding.

Solution:

def isSubsequence(self, s: str, t: str) -> bool:
    if len(s) == 0:
        return True
    if len(t) == 0:
        return False
    temp = ''
    count = 0
    for i in t:
        if count < len(s) and i == s[count]:
            temp  = i
            count  = 1
    if temp == s:
        return True
    else:
        return False

Link: https://leetcode.com/problems/is-subsequence/

CodePudding user response：

As commented the posted solution is Your approach is an example of a two pointer algorithm

To create a Dynamic Programming problems solution we can be broken into three steps

1. Find the first solution (base case)
2. Analyze the solution
3. Optimize the solution

Step 1: First solution

Here's a recursive solution top/down solution that solves the problem.

• Recursive solution breaks into subproblems
• if s is empty string problem solved (return True)
• if t is empty the problem solved (return False)
• if first letters match => return result of matching after first letters in s & t
• otherwise, match s after first letter in t

Code

def isSubsequence(s, t):
    # Base Cases
    if not s:
        return True  # s is empty
    elif not t:
        return False  # t is empty
    # Recursive case
    # if first letters match, solve after first letters of s & t
    # else find s after first letter of t
    return isSubsequence(s[1:], t[1:]) if s[0] == t[0] else isSubsequence(s, t[1:])

Step 2: Analysis

• The recursion provides a simple implementation
• Normally recusion would be inefficient since it would repeatedly solve the same subproblems over and over
• However, subproblems are not repeatedly solved in this case

For instance to find if "ab" is a subsequence of "xaxb" we the following call tree:

isSubsequence("ab", 'xaxb')         # to check "ab" against "xaxb"
  isSubsequence("ab", "axb")          # we check these sequence of subproblems
    isSubsequence("b", "xb")            # but each is only checked once
        isSubsequence("b", "b")
          isSubsequenc("", "")
            return True

Step 3: Optimization

In this case the solution is already optimized. For other recursive solutons like thiw we would use memoization to optimize

• avoids repeatedly solving subsolutions
• can use the cache Python 3.9 or lru_cache (pre Python 3.9) for memoization

Memoized Code (note: not necessary in this case)

   from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def isSubsequence(s, t):
        # Base Cases
        if not s:
            return True  # s is empty
        elif not t:
            return False  # t is empty
        # Recursive case
        # if first letters match, solve after first letters of s & t
        # else find s after first letter of t
        return isSubsequence(s[1:], t[1:]) if s[0] == t[0] else isSubsequence(s, t[1:])