115 Distinct Subsequences 不同子序列

给定一个字符串 S 和一个字符串 T，求 S 的不同的子序列中 T 出现的个数。
一个字符串的一个子序列是指：通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（譬如,"ACE"是"ABCDE" 的一个子序列，而 "AEC" 不是）
下面是一个例子:
S = "rabbbit", T = "rabbit"
返回 3.
详见：https://leetcode.com/problems/distinct-subsequences/description/

Java实现：

class Solution {

    public int numDistinct(String s, String t) {

        int m=s.length();

        int n=t.length();

        //dp[i][j]表示S串中从开始位置到第i位置与T串从开始位置到底j位置匹配的子序列的个数

        int[][] dp = new int[m + 1][n + 1];

        dp[0][0] = 1;//initial

        //如果S串为空，那么dp[0][j]都是0

        for(int j = 1; j <= n; j++){//s is empty

            dp[0][j] = 0;

        }

        //如果T串为空，那么dp[i][j]都是1

        for (int i = 1; i <= m; i++){//t is empty

            dp[i][0] = 1;

        }

        for (int i = 1; i <= m; i++) {

            for (int j = 1; j <= n; j++) {

                dp[i][j] = dp[i - 1][j];

                if (s.charAt(i - 1) == t.charAt(j - 1)) {

                    dp[i][j] += dp[i - 1][j - 1];

                }

            }

        }

        return dp[m][n];

    }

}

参考：https://www.cnblogs.com/springfor/p/3896152.html

巴特西

115 Distinct Subsequences 不同子序列

最新文章

热门文章