0392-判断子序列

技术0392-判断子序列 0392-判断子序列给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串

092-判断子序列

给定字符串S和T,判断S是否是T的子序列。

字符串的子序列是通过从原始字符串中删除一些(或不删除)字符而不改变剩余字符的相对位置而形成的新字符串。(例如,‘ace’是‘abcde’的子序列,而‘AEC’不是)。

高级:

如果有大量的输入S,叫做S1、S2、Sk,其中k=10亿,你需要依次检查它们是否是T的子序列。在这种情况下,您将如何更改代码?

谢谢:

特别感谢@pbrother添加了这个问题并创建了所有测试用例。

例1:

输入:s='abc ',t='ahbgdc '

输出:真

例2:

输入:s='axc ',t='ahbgdc '

输出:假

提示:

0=s .长度=100

0=长度=10^4

两个字符串都只包含小写字符。

资料来源:LeetCode

链接:https://leetcode-cn.com/problems/is-subsequence

参考:

https://leet code-cn.com/problems/is-subseries/solution/Dai-ma-sui-Xiang-Lu-Dai-ni-Xue-tou-dpzi-knntf/

python

# 0392.判断子序列

类别解决方案:

def isSubsequence(self,s:字符串,t:字符串)- bool:

'''

动态规划,编辑距离,时空O(n*m)

1.确定dp和下标

-dp[i][j],下标i-1结尾的S串,下标j-1结尾的T串。相同的子序列长度是dp[i][j]

2.确定重复公式

-如果s [I-1]=t [j-1],则在t中找到的字符也会出现在s中,dp[i][j]=dp[i-1][j-1] 1。

-如果s[i-1]!=t[j-1],相当于删除t中的字符并继续匹配,dp[i][j]=dp[i][j-1]

初始化

- dp[][]=0

4.遍历顺序

外层为S,内层为t。

:参数s:

:参数t:

:return:

'''

DP=[[0]*(len(t)1)for _ in range(len(s)1)]

对于范围(1)中的I,len(s) 1):

对于范围(1)中的j,len(t) 1):

if s[i-1]==t[j-1]:

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

else:

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

if DP[-1][-1]==len :

返回真

False返回

golang

包动态编程

//动态规划

函数问题序列字符串

DP :=make([][][]int,len(s) 1)

对于i :=范围dp {

dp[i]=make([]int,len(t) 1)

}

对于I :=1;i=len我

对于j :=1;j=len(t);j {

if s[i-1]==t[j-1] {

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

} else {

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

}

}

}

if dp[len(s)]

返回真

}

返回false

}

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/134429.html

(0)

相关推荐

  • Linux中系统命令有哪些

    技术Linux中系统命令有哪些小编给大家分享一下Linux中系统命令有哪些,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!ps查看系统中进程状态

    攻略 2021年11月20日
  • SQL优化limit分页的方法是什么

    技术SQL优化limit分页的方法是什么本篇内容介绍了“SQL优化limit分页的方法是什么”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅

    攻略 2021年11月5日
  • 使用chattr +i filename 防止文件误删

    技术使用chattr +i filename 防止文件误删 使用chattr +i filename 防止文件误删chattr +i 设置文件不能进行修改:即你不能删除它
    也不能给它重新命名,你不能对该

    礼包 2021年10月27日
  • 对孩子的期望和鼓励的话,父母对孩子的期望寄语初中生

    技术对孩子的期望和鼓励的话,父母对孩子的期望寄语初中生1家长对初中孩子的期望 1.愿你是一棵树:春天对孩子的期望和鼓励的话,吐一山淡淡的香味;夏天,洒一抹如泉的凉荫;秋天,举一树甜甜的青果;冬天,做一个养精蓄锐的好梦!

    生活 2021年10月21日
  • 抖音怎么刷粉丝,刷抖音粉丝网站最便宜?

    技术抖音怎么刷粉丝,刷抖音粉丝网站最便宜?抖音便宜刷粉网站,刷抖音粉丝网站最便宜抖音刷粉丝的平台网站搜索应该也很多,价格差异也很大,原因主要是看做单的号的质量,有的机器刷单,有的是真人接单,有的是群派单,还有的是真机养的

    测评 2021年10月21日
  • mysql删库语句怎么写

    技术mysql删库语句怎么写这篇文章主要介绍mysql删库语句怎么写,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完! mysql删库语句是“DROP DATABASE [

    攻略 2021年12月9日