LeetCode 115. 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. Subscribe to see which companies asked this question.

题目

给出字符串S和字符串T,计算S的不同的子序列中T出现的个数。 子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串,并且对剩下的字符的相对位置没有影响。(比如,“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。 样例 给出S = "rabbbit", T = "rabbit" 返回 3

分析

利用动态规划去做,我们用dp[i][j]表示S与T的前i个字符与前j个字符的匹配子串个数。可以知道: 1)初始条件:T为空字符串时,S为任意字符串都能匹配一次,所以dp[i][0]=1;S为空字符串,T不为空时,不能匹配,所以dp[0]j=0。 2)若S的第i个字符等于T的第j个字符时,我们有两种匹配的选择:其一,若S的i-1字符匹配T的j-1字符,我们可以选择S的i字符与T的j字符匹配;其二,若S的i-1字符子串已经能与T的j字符匹配,放弃S的i字符与T的j字符。因此这个情况下,dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。 3)若S的第i个字符不等于T的第j个字符时,这时只有当S的i-1字符子串已经能与T的j字符匹配,该子串能够匹配。因此这个情况下,dp[i][j]=dp[i-1][j]。

代码

public class Solution {
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    public int numDistinct(String S, String T) {
        // write your code here
        if (S == null || T == null) {
            return 0;
        }

        int[][] nums = new int[S.length() + 1][T.length() + 1];

        for (int i = 0; i <= S.length(); i++) {
            nums[i][0] = 1;
        }
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                nums[i][j] = nums[i-1][j];
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    nums[i][j] += nums[i - 1][j - 1];
                }
            }
        }
        return nums[S.length()][T.length()];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术博客

C#类和结构体的异同点简单总结

类和结构的异同点? 异:  1.关键字不同 一个是class,一个是struct     2.类型不同,一个是引用类型,一个是值类型(一个堆区,一个栈区)   ...

52620
来自专栏一“技”之长

JavaScript基础之二——方法与属性 原

    和编译型语言必须由类产生对象不同,JavaScript语言中并没有严格的类的界定,并且对象的属性和方法也可以进行动态的绑定。属性是对象中封装的一些值数据...

7320
来自专栏null的专栏

LeetCode——Longest Substring Without Repeating Characters

题目: Given a string, find the length of the longest substring without repeating c...

33940
来自专栏数据结构与算法

35:字符串的展开 5分,实在无能为力

35:字符串的展开 总时间限制: 1000ms 内存限制: 65536kB描述 在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如...

36070
来自专栏数据结构与算法

35:字符串的展开

35:字符串的展开 总时间限制: 1000ms 内存限制: 65536kB描述 在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如...

39950
来自专栏about云

spark开发基础之Scala详解apply方法

问题导读 1.什么情况下调用apply方法? 2.apply你认为有哪些作用? 3.方法调用属于apply什么功能? apply网上很多资料,但是总感觉总...

39860
来自专栏Phoenix的Android之旅

Java 强/弱/软引用

来排列。在JVM运行内存不足时,这三种之中最先被回收的是 弱引用,依次到最后才是强引用(不会被回收)。 但是对于强引用来说,JVM在内存不足时宁可抛出 OOM,...

11620
来自专栏chenjx85的技术专栏

leetcode-541-Reverse String II

16750
来自专栏LanceToBigData

Java常用类(一)之Object类详解

大家都知道Object是所有类的父类,任何类都默认继承Object 理论上Object类是所有类的父类,即直接或间接的继承java.lang.Object类。由...

27480
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--递归

递归是很多算法都使用的一种编程方法。听说递归是一种十分优雅的问题解决办法,可是对于初涉递归的我,还没有形成这种独特的体会。 学习使用递归的关键在于:如何将问题分...

31280

扫码关注云+社区

领取腾讯云代金券