不同的子序列

yingl · yingl · commit 0c18ac8c0d90 · 2016-09-23T15:46:49.000+08:00
diff --git a/distinct_subsequences.py b/distinct_subsequences.py
@@ -0,0 +1,27 @@
+class Solution: 
+    # @param S, T: Two string.
+    # @return: Count the number of distinct subsequences
+    def numDistinct(self, S, T):
+        # write your code here
+        '''
+        根据题目提供的例子，建一张二维表：
+            r a b b b i t (S)
+        r 0 1 1 1 1 1 1 1   
+        a 0 0 1 1 1 1 1 1
+        b 0 0 0 1 2 3 3 3
+        b 0 0 0 0 1 3 3 3 ＃ 关键在第一个3
+        i 0 0 0 0 0 0 3 3
+        t 0 0 0 0 0 0 0 3
+        (T)
+        dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)
+        '''
+        rows = len(T) + 1
+        cols = len(S) + 1
+        caches = [[0] * cols for i in xrange(rows)]
+        caches[0] = [1] * cols
+        for i in xrange(1, rows):
+            for j in xrange(1, cols):
+                caches[i][j] = caches[i][j - 1]
+                if T[i - 1] == S[j - 1]:
+                    caches[i][j] += caches[i - 1][j - 1]
+        return caches[-1][-1]
