[Leetcode] Distinct Subsequences 不同顺序字串

SnaiLiu 发布于2019-08-14 16:11 / 2503人阅读

摘要：计算元素值时，当末尾字母一样，实际上是左方数字加左上方数字，当不一样时，就是左方的数字。示意图代码如果这个字符串有个怎么办用暴力法，对每一位开始向后检查是否是。

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.

原题链接

动态规划法 复杂度

时间 O(NM) 空间 O(NM)

思路

这题的思路和EditDistance有些相似，我们需要一个二维数组dp(i)(j)来记录长度为i的字串在长度为j的母串中出现的次数，这里长度都是从头算起的，而且遍历时，保持子串长度相同，先递增母串长度，母串最长时再增加一点子串长度重头开始计算母串。

首先我们先要初始化矩阵，当子串长度为0时，所有次数都是1，当母串长度为0时，所有次数都是0.当母串子串都是0长度时，次数是1（因为都是空，相等）。接着，如果子串的最后一个字母和母串的最后一个字母不同，说明新加的母串字母没有产生新的可能性，可以沿用该子串在较短母串的出现次数，所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一个字母和母串的最后一个字母相同，说明新加的母串字母带来了新的可能性，我们不仅算上dp(i)(j-1)，也要算上新的可能性。那么如何计算新的可能性呢，其实就是在既没有最后这个母串字母也没有最后这个子串字母时，子串出现的次数，我们相当于为所有这些可能性都添加一个新的可能。所以，这时dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。下图是以rabbbit和rabbit为例的矩阵示意图。计算元素值时，当末尾字母一样，实际上是左方数字加左上方数字，当不一样时，就是左方的数字。

示意图

     0    r    a    b    b    b    i    t
0    1    1    1    1    1    1    1    1
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
i    0    0    0    0    0    0    3    3
t    0    0    0    0    0    0    0    3

代码

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

Follow Up

Q：如果这个字符串有1000000个char怎么办？
A：用暴力法，对每一位开始向后检查是否是subsequence。

超融合服务器专线服务不同顺序排列 Subsequences LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66165.html

[LintCode/LeetCode] Distinct Subsequences [一维DP]

摘要：用动规方法做建立长度为和的二维数组，表示的第到位子串包含不同的的第到位子串的个数。初始化当的子串长度为时，当的子串长度为时，当和子串都为时，包含，故。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a strin...

dailybird 2019-08-14 15:29 评论0 收藏0
leetcode115. Distinct Subsequences

摘要：题目要求判断字符串中通过删减单词含有几个字符串。例如中含有个字符串，通过分别删除第，，个。也就是说，我们需要通过一个数据结构来记录临时结果从而支持我们在已知前面几个情况的场景下对后续情况进行计算。题目要求 Given a string S and a string T, count the number of distinct subsequences of S which equa...

NSFish 2019-08-16 10:44 评论0 收藏0
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 str...

LittleLiByte 2019-08-14 17:59 评论0 收藏0
Distinct Subsequences

摘要：终于见到一个使用动态规划的题目了，似乎这种字符串比对的差不多都是的思路。从后向前递推，我们可以得到下面的矩阵可以看出，矩阵中每个的数值为，这样右下角的值即为所求。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of...

Ajian 2019-07-24 17:32 评论0 收藏0
[LeetCode] 491. Increasing Subsequences

Problem Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example: ...

wupengyu 2019-08-16 13:50 评论0 收藏0