推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 教你写算法 > 动态规划在字符串比对中的应用

动态规划在字符串比对中的应用

教你写算法 2019-02-13

今天的题目是这样的,说给了两个字符串s和t,求解s的subsequence到底有几种可以构成t的方法。

例如s = rabbbit, t = rabbit。这里就是三种

s = babgbag, t = bag。这里是五种。


常规解法:

首先需要一个指针b指向t的首字母,然后在s里面找到b指针所指的字母,移动b指针,依次类推。这种方法很好理解,但是实现起来很麻烦,时间复杂度达到了O(m²n)。


Dynamic Programming:

我们拿第二个例子进行举例说明。

首先当s = b,t = b的时候,很明显答案是1。扩大一下s,s = ba,t = b的时候,答案还是1。于是我们可以得到下面这个表格

接下来,我们继续扩大s。

动态规划在字符串比对中的应用

然后我们扩大t。

动态规划在字符串比对中的应用

最后我们可以写出整个的表格为:

这里我要解释一下表格的第二排和第二列。如果当s和t均为空的时候很明显答案是1。如果当s为空,t为非空的时候,很明显答案是0。如果当t为空s非空的时候答案很明显也是1。

通过观察表格,我们可以发现,当s[j] = t[i]的时候,table[i][j] = table[i-1][j-1] + table[i][j-1]。当s[j] != t[i]的时候,table[i][j] = table[i][j-1]。

不等的情况很好理解就不做概述了。等于的情况我在这里解释一下,我们已知“bab”里面含有两个b,含有一个ba,然后我要在后面加上一个a问含有几个ba。因为已经含有两个b了所以答案是原来的1个ba再加上新出现2个ba,答案是3。

理解了通项公式,代码就不难写出了。

时间复杂度和空间复杂度均为O(mn)。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《动态规划在字符串比对中的应用》的版权归原作者「教你写算法」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注教你写算法微信公众号

教你写算法微信公众号:Write_algorithm

教你写算法

手机扫描上方二维码即可关注教你写算法微信公众号

教你写算法最新文章

精品公众号随机推荐