• 代码随想录算法训练营day55 | 392.判断子序列,115.不同的子序列


    392.判断子序列

    参考代码随想录算法训练营第五十五天 |392. 判断子序列、115. 不同的子序列 - 掘金

    • 暴力解法: Time Complexity: O(M*N)  Space Complexity: O(N)

    1. class Solution:
    2. def isSubsequence(self, s: str, t: str) -> bool:
    3. start = 0 #used to make sure that the relative positions do not change
    4. for char in s:
    5. t = t[start:]
    6. idx = t.find(char)
    7. if idx == -1:
    8. return False
    9. start = idx + 1
    10. return True
    • 双指针:同时操作两个数组: Time Complexity: O(N)  Space Complexity: O(1)

    1. class Solution(object):
    2. def isSubsequence(self, s, t):
    3. """
    4. :type s: str
    5. :type t: str
    6. :rtype: bool
    7. """
    8. pointerS = 0
    9. pointerT = 0
    10. while pointerT < len(t):
    11. if pointerS >= len(s):
    12. break
    13. if t[pointerT] == s[pointerS]:
    14. pointerS += 1
    15. pointerT += 1
    16. return pointerS == len(s)
    • 动态规划: Time Complexity: O(M*N)  Space Complexity: O(M*N)

    五部曲:

    1. 确定dp数组以及下标的含义:

        dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同。序列的          长度为dp[i][j]

    2. 确定递推公式:

        首先要考虑如下两种操作:

    • if (s[i - 1] == t[j - 1]):也就是t中找到了一个字符在s中也出现了。那么dp[i][j] = dp[i - 1][j - 1] + 1;,因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]的基础上加1
    • if (s[i - 1] != t[j - 1]):也就是相当于t要删除元素,继续匹配。t如果把当前元素t[j - 1]删除,那么dp[i][j] 的数值就是看s[i - 1]与 t[j - 2]的比较结果了,即:dp[i][j] = dp[i][j - 1];

    3. dp数组如何初始化:从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],         所。以dp[0][0]和dp[i][0]是一定要初始化的。dp[i][0] 表示以下标i-1为结尾的字符串,与空字符串的相同子序列长度,所以为0. dp[0][j]同理。

    (这里大家已经可以发现,在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符         串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。因为这样的定义在dp二       维矩阵中可以留出初始化的区间。如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t,初始化就比较麻烦了。)

    这与#718,#1143和#1035对于dp数组的定义出于同样的目的,都是可以简化初始化过程。二刷时确定一下按照哪个方式来写,固定下来

    4. 确定遍历顺序:从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],那么遍历顺序也应该是从上到下,从左到右

    5. 打印检查

    注意:

    • dp数组的定义:以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。 就是求s和t的相同子序列,换句话说和求t和s的相同子序列是一样的。(不同于暴力解法,要明确一个是另一个的子序列,或者说明确字符串长短;动态规划是求两个字符串的公共子序列,因此dp数组的定义关于t和s谁在前谁在后无所谓,下面代码就是调换s和t的位置。)
    1. class Solution(object):
    2. def isSubsequence(self, s, t):
    3. """
    4. :type s: str
    5. :type t: str
    6. :rtype: bool
    7. """
    8. dp = [[0]*(len(s)+1) for _ in range(len(t)+1)]
    9. # print(dp)
    10. for i in range(1, len(t)+1):
    11. for j in range(1, len(s)+1):
    12. if t[i - 1] == s[j - 1]:
    13. dp[i][j] = dp[i-1][j-1]+1
    14. else:
    15. dp[i][j] = dp[i-1][j]
    16. return dp[len(t)][len(s)] == len(s)

    115.不同的子序列

    Q:#392在定义dp数组时是dp = [[0]*(len(t)+1) for _ in range(len(s)+1)](s is a subsequence of t);这道题是t is a subsequence of s,dp数组定义也是dp = [[0] * (len(t)+1) for _ in range(len(s)+1)],为什么可以这样?

    A: 参考上面“注意”的讨论

    1. class Solution(object):
    2. def numDistinct(self, s, t):
    3. """
    4. :type s: str
    5. :type t: str
    6. :rtype: int
    7. """
    8. dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
    9. print(dp)
    10. for i in range(len(s)):
    11. dp[i][0] = 1
    12. for j in range(1, len(t)):
    13. dp[0][j] = 0
    14. for i in range(1, len(s)+1):
    15. for j in range(1, len(t)+1):
    16. if s[i-1] == t[j-1]:
    17. dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    18. else:
    19. dp[i][j] = dp[i-1][j]
    20. return dp[len(s)][len(t)]

  • 相关阅读:
    [DDC]Deep Domain Confusion: Maximizing for Domain Invariance
    数据结构:二叉树基础
    【ElasticSearch】学习使用DSL和RestClient编写查询语句
    「Git|场景案例」从项目中删除之前commit过的文件并且让git不追踪删除操作
    springboot+校园超市管理系统的设计与实现 毕业设计-附源码201521
    金仓数据库KingbaseES安全指南--6.7. GSSAPI身份验证
    玩转代码| Vue 中 JSX 的特性,这一篇讲的明明白白
    登录功能(基于SpringBoot+MP+Vue实现的功能)
    PLM是什么?为什么要上PLM?有什么好处?
    安全监控系统管理制度
  • 原文地址:https://blog.csdn.net/jzh013/article/details/128030314