[Leetcode][python]Distinct Subsequences/不同子序列

淩亂°似流年 2022-06-06 09:14 193阅读 0赞

## 题目大意 ##

给定S和T两个字符串，问把通过删除S中的某些字符，把S变为T有几种方法？

## 解题思路 ##

动态规划,设dp\[i\]\[j\]为到S\[i\] T\[j\]位置的方法数：

dp[i][0]=1 (T为空的话，S只能全部删除）
    S[i]==T[j] : dp[i][j]=dp[i-1][j] + dp[i-1][j-1] （两字符串相等，要么跳过不匹配+要么匹配）
    S[i]!=T[j]: dp[i][j]=dp[i-1][j] （不相等只能不匹配这个）

**同样你可以打印出dp看结构:上半区都为0，因为不可能，dp\[0\]\[0\]为1因为空转空有一种可能（不删除）**

例子：Rabbit Rabbbit

\ X  r  a  b  b  i  t
    X[1, 0, 0, 0, 0, 0, 0]
    r[1, 1, 0, 0, 0, 0, 0]
    a[1, 1, 1, 0, 0, 0, 0]
    b[1, 1, 1, 1, 0, 0, 0]
    b[1, 1, 1, 2, 1, 0, 0]
    b[1, 1, 1, 3, 3, 0, 0]
    i[1, 1, 1, 3, 3, 3, 0]
    t[1, 1, 1, 3, 3, 3, 3]

## 代码 ##

class Solution(object):
        def numDistinct(self, s, t):
            """
            :type s: str
            :type t: str
            :rtype: int
            """
            m , n = len(s),len(t)
            dp =[[0 for j in range(n+1)]for i in range(m+1)]
            for i in range(0, m+1): 
                dp[i][0]=1
            for i in range(1, m+1):
                for j in range(1, n+1):
                    if s[i-1]==t[j-1]:  # 这里比较的实际是s[i]t[j]，只是由于dp表所以向后扩展了一位 
                        dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
                    else:
                        dp[i][j]=dp[i-1][j]
            return dp[m][n]

## 总结 ##

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关 115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的

迈不过友情╰/ 2023年09月30日 09:16/ 0 赞/ 20 阅读

相关 Longest Common Subsequence（C++最长公共子序列）

解题思路：（1）动态规划 class Solution { public: int longestCommonSubsequence(st

谁践踏了优雅/ 2023年01月17日 04:57/ 0 赞/ 200 阅读

相关 Subsequence 子序列

Subsequence 191221 > 答案思路英文题翻译为中文 Title 题目： A sequence of N positive integers (

悠悠/ 2022年12月29日 09:11/ 0 赞/ 147 阅读

相关 LeetCode | 0491. Increasing Subsequences递增子序列【Python】

> LeetCode 0491. Increasing Subsequences递增子序列【Medium】【Python】【DFS】 Problem [LeetCode

曾经终败给现在/ 2022年12月01日 03:54/ 0 赞/ 182 阅读

相关 leetcode 115. Distinct Subsequences Hard | 115. 不同的子序列（动态规划）

题目 [https://leetcode.com/problems/distinct-subsequences/][https_leetcode.com_problems

约定不等于承诺〃/ 2022年10月18日 15:49/ 0 赞/ 72 阅读

相关 Distinct Subsequences（C++不同的子序列）

（1）通配符匹配类似，取不取都要算 class Solution { public: int numDistinct(string s, st

客官°小女子只卖身不卖艺/ 2022年10月13日 05:23/ 0 赞/ 146 阅读

相关 leetcode 491. Increasing Subsequences | 491. 递增子序列（Java）

题目 [https://leetcode.com/problems/increasing-subsequences/][https_leetcode.com_proble

浅浅的花香味﹌/ 2022年09月10日 12:13/ 0 赞/ 164 阅读

相关 392. Is Subsequence （子序列判断）

Given a string s and a string t, check if s is subsequence of t. You may assume that th

川长思鸟来/ 2022年07月14日 05:27/ 0 赞/ 153 阅读

相关 [Leetcode][python]Distinct Subsequences/不同子序列

题目大意给定S和T两个字符串，问把通过删除S中的某些字符，把S变为T有几种方法？解题思路动态规划,设dp\[i\]\[j\]为到S\[i\] T\[j\]位

淩亂°似流年/ 2022年06月06日 09:14/ 0 赞/ 194 阅读

相关 LeetCode: 392. Is Subsequence 是否是子序列

试题： Given a string s and a string t, check if s is subsequence of t. You may assume t

ゝ一世哀愁。/ 2021年06月24日 16:10/ 0 赞/ 327 阅读