DP

FazeelUsmani · FazeelUsmani · commit a0ce9e6e7e8e · 2021-09-20T23:59:49.000+05:30
diff --git a/09 September Challenge 2021/19_distinct_subsequences.py b/09 September Challenge 2021/19_distinct_subsequences.py
@@ -0,0 +1,12 @@
+class Solution:
+    def numDistinct(self, s: str, t: str) -> int:
+        @lru_cache(None)
+        def dp(i, j):
+            if j == 0: return 1  # Case t = "", there is a valid subsequence which is empty string.
+            if i == 0: return 0
+            ans = dp(i - 1, j)
+            if s[i-1] == t[j-1]:
+                ans += dp(i - 1, j - 1)
+            return ans
+
+        return dp(len(s), len(t))
