Distinct Subsequences https://leetcode.com/problems/distinct-subsequences/?tab=Description
- This question requires re-wording. Here is a better description http://www.programcreek.com/2013/01/leetcode-distinct-subsequences-total-java/:
"Given a string S and a string T, count the number of distinct subsequences of S which equals T."
"How many ways can you generate the string T by only removing (but not reordering) characters in S?"
- The next thing we need to do is come up with a way to divide this problem and subsequently come up with a recurrence.
- dp[i,j]: How many subsequences of s[0:j-1] are equal to t[0:i-1]?
- dp[i,j] = dp[i-1,j-1] + dp[i, j-1] if t[i-1] == s[j-1]
- dp[i,j] = dp[i, j-1] if t[i-1] != s[j-1]
- Note i and j are respective lengths.
- What are the boundary conditions? Refer to code.
- What is the order of filling up the array? row-wise.
- Picture and explanation:https://discuss.leetcode.com/topic/9488/easy-to-understand-dp-in-java
- Another explanation:https://discuss.leetcode.com/topic/6465/a-dp-solution-with-clarification-and-explanation
class Solution(object): def numDistinct(self, s, t): """ :type s: str :type t: str :rtype: int """ N, M = len(t), len(s) dp = [*(M+1) for _ in range(N+1)] for i in range(N+1): dp[i] = 0 # How many subsequences of zero length S can be formed which equal t[0:i] for j in range(M+1): dp[j] = 1 # How many subsequences of S[0:j] can be formed which equal t[0:1] for i in range(1, N+1): for j in range(1, M+1): if t[i-1] == s[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i][j-1] else: dp[i][j] = dp[i][j-1] return dp[N][M]
from collections import defaultdict class Solution(object): def helper(self, i, j, s, t, cache): if i == len(s) and j == len(t): return 1 elif i == len(s): return 0 elif j == len(t): return 1 elif i in cache and j in cache[i]: return cache[i][j] elif s[i] == t[j]: # Include or Do Not Include return self.helper(i+1, j+1, s, t, cache) + self.helper(i+1, j, s, t, cache) else: return self.helper(i+1, j, s, t, cache) def numDistinct(self, s, t): """ :type s: str :type t: str :rtype: int """ cache = defaultdict(dict) return self.helper(0,0,s,t,cache)