Leetcode Problem 115. Distinct Subsequences

115. Distinct Subsequences

Leetcode Solutions

Approach: Recursion + Memoization

  1. Define a helper function recurse(i, j) that takes indices i and j as arguments.
  2. If j is equal to the length of t, return 1 (base case).
  3. If i is equal to the length of s, return 0 (base case).
  4. Check if the result for recurse(i, j) is already in the memoization dictionary. If yes, return the cached result.
  5. If s[i] matches t[j], recursively call recurse(i + 1, j + 1) to move both pointers forward and add the result to recurse(i + 1, j) where only the i pointer is moved.
  6. If s[i] does not match t[j], recursively call recurse(i + 1, j).
  7. Cache the result in the memoization dictionary before returning it.
  8. Call recurse(0, 0) to start the recursion with both pointers at the beginning of s and t.
UML Thumbnail

Approach: Iterative Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...