leetcode: Distinct Subsequences

问题描述：

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

原问题链接：https://leetcode.com/problems/distinct-subsequences/

 

问题分析

　　这个问题相对来说比较难找到思路。对于给定的源串s来说，要让它的子串能够构成目标串t，那么理论上可能是它里面的任何一个元素可能存在或者删除。如果按照这个思路，假设源串长度为m的话，那么对它里面每种情况进行构造并和目标串比较的可能性有2 ** m次。这种情况将使得解决方法不可接受。因此，我们需要根据原来的问题描述来寻找一个它们关系推导的规律。

　　假设对于s来说，它的当前位置为i，对于t来说它的当前位置为j。那么当s.charAt(i)  != t.charAt(j)的时候，说明s串里i这个位置的元素必须被删除才行，否则没法匹配。这个时候它们的可能构成数量和s[i - 1], t[j]的值相同。那么，当s.charAt(i) == t.charAt(j)的话呢？那么s[i - 1], t[j - 1]的情况是一种选择。而s[i - 1], t[j]也是一种选项。这个地方有点难以理解，为什么s[i - 1], t[j]也是一种选项呢？因为我们在前面的问题定义里，对于s来说它里面每个元素可能存在也可能删除。那么当删除第i个元素的时候，也有可能它前面的i - 1个元素和t中间的j个元素也构成了符合条件的序列，所以这种情况也应该包含进来。

　　按照这个思路，我们可以定义一个二维矩阵int[][] matrix，它是一个(m + 1) x (n + 1)的矩阵。在最开始的时候，其中m, n分别表示s和t的长度。matrix[][]里有一个初始条件，就是matrix[i][0] = 1。就是说，对于任意长度的源串s，对应于一个空串t来说，它都有一个子串，也就是删除它所有的字符。而对于其他的情况，则按照我们前面讨论的针对s.charAt(i - 1) == t.charAt(j - 1)的情况来处理。

　　于是我们可以得到如下的代码实现：

 

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        if(n > m) return 0;
        int[][] matrix = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++) matrix[i][0] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                matrix[i][j] = matrix[i - 1][j] + (s.charAt(i - 1) == t.charAt(j - 1) ? matrix[i - 1][j - 1] : 0);
            }
        }
        return matrix[m][n];
    }
}

　　这种实现的时间复杂度和空间复杂度基本上都是O(m * n) 。

 

改进

　　在上述的代码实现中，我们还有一个可以改进的细节，就是对于空间的使用。前面的二维数组可以缩小为一维的数组，因为我们这里只需要保留t里面对应每个长度的匹配个数，我们可以重用之前的结果。

　　这种方式实现的代码如下：

 

public class Solution {
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        if(m > n) return 0;
        int[] path = new int[m + 1];
        path[0] = 1;
        for(int j = 1; j <= n; j++) {
            for(int i = m; i >= 1; i--) {
                path[i] = path[i] + (t.charAt(i - 1) == s.charAt(j - 1) ? path[i - 1] : 0);
            }
        }
        return path[m];
    }
}