1638 统计只差一个字符的子串数目(动态规划)

标签: 力扣  动态规划

1. 问题描述:

给你两个字符串 s 和 t ,请你找出 s 中的非空子串的数目,这些子串满足替换一个不同字符以后,是 t 串的子串。换言之,请你找到 s 和 t 串中恰好只有一个字符不同的子字符串对的数目。比方说, "computer" 和 "computation" 加粗部分只有一个字符不同: 'e'/'a' ,所以这一对子字符串会给答案加 1 。请你返回满足上述条件的不同子字符串对数目
一个 子字符串是一个字符串中连续的字符。

示例 1:

输入:s = "aba", t = "baba"
输出:6
解释:以下为只相差 1 个字符的 s 和 t 串的子字符串对:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
加粗部分分别表示 s 和 t 串选出来的子字符串。

示例 2:

输入:s = "ab", t = "bb"
输出:3
解释:以下为只相差 1 个字符的 s 和 t 串的子字符串对:
("ab", "bb")
("ab", "bb")
("ab", "bb")
加粗部分分别表示 s 和 t 串选出来的子字符串。

示例 3:

输入:s = "a", t = "a"
输出:0

示例 4:

输入:s = "abe", t = "bbc"
输出:10

提示:

  • 1 <= s.length, t.length <= 100
  • s 和 t 都只包含小写英文字母。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-substrings-that-differ-by-one-character

2. 思路分析:

① 一开始的时候想了好久没有啥思路,于是看了一下力扣的题解,发现可以使用动态规划的思路解决,其中发现一位大佬的二维dp写的比较好,我结合pycharm中的debug与测试用例s = "ab", t = "bb"进行调试,理解每一句代码表达的意思,下面是我自己的一些理解:

② 其中使用的是二维的dp来解决的(二维的列表),dp[i][j] = (x, y)的意思表示的是以s中以字符s[i - 1]结尾,t中以t[j - 1]结尾的子串中完全相同的个数x与只有一个字符不同的个数的y,感觉在代码中的体现真的非常棒(一开始的时候只看代码感觉有点疑惑,后面理解了发现为什么可以这么巧妙),其中需要在声明的二维列表的长度为len(s) + 1, len(t) + 1,其中第一行与第一列是用来处理边界上的问题,并且声明两个变量zero,one来记录以s[i - 1],t[j - 1]的子串完全相同与只有一个字符不同的数目,并且根据当前s[i - 1]与t[j - 1]比较之后的结果来更新这两个变量并且将对应的值放入到dp[i][j]中,这里存在两种情况,当前比较的s[i - 1] == t[j - 1]这个时候对zero加1即可,当不相等的时候那么one = zero + 1, zero = 0表示两个子串完全相同的数量为0了,不相同的数量为之前记录的zero的数量上加1即可,因为每一次比较的时候字符串都是不一样的所以需要在循环的时候累加只相差一个字符的数目到结果集中,这里可以累加one的值即可,结合具体的例子会更好理解一点,感觉最重要的是需要理解当前的dp[i][j]只与s中上一个字符,t中上一个字符的dp[i - 1][j - 1]的值有关,在代码中的体现就有点像暴力枚举每一种情况(枚举以当前字符结尾对应长度的字符的组合情况这个思路很巧妙),但是与暴力不同的是比暴力的时间复杂度要小,因为它每一次都是在上一次的基础上进行递推得到的,下面是一个例子对应的图示:

3. 代码如下:(大佬的题解网址)

大佬的代码:

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        len_s, len_t = len(s), len(t)
        dp = [[(0,0)]*(len_t+1) for _ in range(len_s+1)] 
        res = 0
        for i in range(1, len_s+1):
            for j in range(1, len_t+1):
                zero, one = dp[i-1][j-1]
                if s[i-1] == t[j-1]:
                    zero += 1
                else:
                    one = zero + 1
                    zero = 0
                dp[i][j] = (zero, one)
                res += one
        return res

 

版权声明:本文为qq_39445165原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39445165/article/details/109601232

智能推荐

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

猜你喜欢

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...

springboot 过滤器Filter vs 拦截器Interceptor 详解

1 前言       最近接触到了过滤器和拦截器,网上查了查资料,这里记录一下,这篇文章就来仔细剖析下过滤器和拦截器的区别与联系。 2 拦截器与过滤器之间的区别 从上面对拦截器与过滤器的描述来看,它俩是非常相似的,都能对客户端发来的请求进行处理,它们的区别如下: 作用域不同 过滤器依赖于servlet容器,只能在 servlet容器,web环境下使用 拦截器依赖于sp...

IDEA环境--JavaWeb项目【分页功能实现】

参考链接:https://www.jianshu.com/p/d108d0cd9acf 1、前言 最近在写一些项目,遇到要使用分页功能的地方,就简单的学习了一下,在此总结一下具体实现的过程以及遇到的问题。 分页功能:当我们写一下web项目时会遇到一个页面要显示很多数据,一下子都显示出来效率会很低,也不美观。这就要用到分页,其作用也就是将数据分割成多个页面来进行显示。 2、项目介绍 这只是一个简单的...

517【毕设课设】基于单片机仓库家庭防火防盗报警系统

【资源下载】下载地址如下: https://docs.qq.com/doc/DTlRSd01BZXNpRUxl 功能简要说明: 1.51单片机+1602液晶+按键+烟雾检测传感器MQ+红外检测+蜂鸣器+DHT11温湿度传感器; 2.按键设置烟雾报警浓度值,温度报警值; 3.当达到报警条件,蜂鸣器响; 5.电路板为PCB腐蚀所做,图文件为altiumdesigner工程文件。 6.程序采用C语言编写...