当前位置: 首页 > news >正文

Leetcode.1638 统计只差一个字符的子串数目

题目链接

Leetcode.1638 统计只差一个字符的子串数目 Rating : 1745

题目描述

给你两个字符串 st,请你找出 s中的非空子串的数目,这些子串满足替换 一个不同字符 以后,是 t串的子串。换言之,请你找到 st串中 恰好 只有一个字符不同的子字符串对的数目。

比方说, "computer"and "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<=1001 <= s.length, t.length <= 1001<=s.length,t.length<=100
  • st都只包含小写英文字母。

解法:dp

对于 s我们可以考虑每次以 s[i](0≤i<n)(0 \leq i < n)(0i<n)开始的 s的子串s't进行匹配。

s't进行匹配时,不同字符数量为 d。当 d == 1时,答案 +1。当 d > 1时,退出循环,接着匹配以 s[i+1]为起点的子串。

时间复杂度:O(m∗n∗min(m,n))O(m*n*min(m,n))O(mnmin(m,n))

C++代码:

class Solution {
public:int countSubstrings(string s, string t) {int m = s.size() , n = t.size();int ans = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){int d = 0;for(int k = 0;i + k < m && j + k < n;k++){d += (s[i + k] != t[j + k]);if(d > 1) break;if(d == 1) ans++;}}}return ans;}
};

Python代码:

class Solution:def countSubstrings(self, s: str, t: str) -> int:m , n = len(s) , len(t)ans = 0for i in range(m):for j in range(n):d , k = 0 , 0while i + k < m and j + k < n:d = d + (1 if s[i + k] != t[j + k] else 0)if d > 1:breakif d == 1:ans = ans + 1k = k + 1return ans

相关文章:

Leetcode.1638 统计只差一个字符的子串数目

题目链接 Leetcode.1638 统计只差一个字符的子串数目 Rating &#xff1a; 1745 题目描述 给你两个字符串 s和 t&#xff0c;请你找出 s中的非空子串的数目&#xff0c;这些子串满足替换 一个不同字符 以后&#xff0c;是 t串的子串。换言之&#xff0c;请你找到 s和 t串中 恰…...

KoTime:v2.3.9新增线程管理(线程统计、状态查询等)

功能概览 KoTime的开源版本已经迭代到了V2.3.9&#xff0c;目前功能如下&#xff1a; 实时监听方法&#xff0c;统计运行时长web展示方法调用链路&#xff0c;瓶颈可视化追踪追踪系统异常&#xff0c;精确定位到方法接口超时邮件通知&#xff0c;无需实时查看线上热更新&…...

直面风口,未来不仅是中文版ChatGPT,还有AGI大时代在等着我们

说到标题的AI2.0这个概念的研究早在2015年就研究起步了&#xff0c;其实大家早已知道&#xff0c;人工智能技术必然是未来科技发展战略中的重要一环&#xff0c;今天我们就从AI2.0入手&#xff0c;以GPT-4及文心一言的发布为切入角度&#xff0c;来谈一谈即将降临的AGI时代。 关…...

若依微服务(ruoyi-cloud)保姆版容器编排运行

一、简介 项目gitee地址&#xff1a;https://gitee.com/y_project/RuoYi-Cloud 由于该项目运行有很多坑&#xff0c;大家可以在git克隆拷贝到本地后&#xff0c;执行下面的命令使master版本回退到本篇博客的版本&#xff1a; git reset --hard 05ca78e82fb4e074760156359d09a…...

vue2图片预览插件

学习&#xff1a;vue插件开发实例-图片预览插件 vue2-pre-img-plugin的gitee代码 准备工作 准备图片与基础的样式 将iconfont下载的字体图标资源放在src/assets/iconfont目录下将准备预览的图片放到src/static/images目录下 PrevImg.vue 在plugins/PrevImg目录下&#xff…...

手写Promise源码的实现思路

Promise的使用&#xff1a; let promise new Promise((resolve, reject) > {resolve("OK");// reject("Error"); });console.log(promise);promise.then(value > {console.log("success"); }, error > {console.log("fail"…...

【数据结构】-关于树的概念和性质你了解多少??

作者&#xff1a;小树苗渴望变成参天大树 作者宣言&#xff1a;认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 &#xff0c;就 给 作 者 点 点 关 注 吧&#xff01; 树前言一、树概念及结构1.1树的概念1.2 树的相关概念1.3 树的表示1.4树在实际中的运用…...

【前端之旅】NPM必知必会

一名软件工程专业学生的前端之旅,记录自己对三件套(HTML、CSS、JavaScript)、Jquery、Ajax、Axios、Bootstrap、Node.js、Vue、小程序开发(UniApp)以及各种UI组件库、前端框架的学习。 【前端之旅】Web基础与开发工具 【前端之旅】手把手教你安装VS Code并附上超实用插件…...

Android SQLite使用事务来确保所有语句都以原子方式执行及保证数据完整性一次执行多条语句示例

execSQL 不支持用分号分隔一次执行多个 SQL 语句&#xff0c;虽然理论上可以实现。但是&#xff0c;并不建议这样做&#xff0c;因为这可能会导致潜在的 SQL 注入漏洞。相反&#xff0c;建议使用 execSQL 或 rawQuery 分别执行每个语句。 在下面的代码块中&#xff0c;我们正在…...

nodejs+vue校园超市小卖部零食在线购物商城系统

21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认识&#xff0c;科学化的管理&#xff0c;使信息存储达到…...

Karl Guttag:论相机对焦技术在AR/VR中的沿用

近期&#xff0c;AR/VR光学专家Karl Guttag介绍了两家在CES 2023展出光学传感技术的公司&#xff1a;poLight和CML&#xff08;剑桥机电一体化&#xff09;。​同时介绍两家公司的原因&#xff0c;是因为他们提供了实现AR/VR“光学微动”&#xff08;Optics Micromovement&…...

ECL@SS学习笔记(3)-概念数据模型

ECLSS 是产品&#xff0c;服务的分类和描述系统。本文介绍其内部的数据模型。ECLSS的作用ECLSS 标准的目标是为了实现工业界数据交换的标准化。这个标准主要作用是产品的分类和描述。分类为了有效地物料管理&#xff0c;供应链管理和电子商务&#xff0c;需要对物料进行分类和编…...

206. 反转链表

给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a; 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1] 示例 3&#xff1a; 输…...

文心一言 vs GPT-4 —— 全面横向比较

文心一言 vs GPT-4 —— 全面横向比较 3月15日凌晨&#xff0c;OpenAI发布“迄今为止功能最强大的模型”——GPT-4。我第一时间为大家奉上了体验报告《OpenAI 发布GPT-4——全网抢先体验》。 时隔一日&#xff0c;3月16日下午百度发布大语言模型——文心一言。发布会上&#…...

rancher2.6进阶之kubectl安装

rancher2.6进阶之kubectl安装 1.安装kubectl客户端 1.1.1.使用命令行下载安装包: curl -LO https://dl.k8s.io/release/$(curl -L -s https://dl.k8s.io/release/stable.txt)/bin/linux/amd64/kubectl Note: 可指定下载版本, 将 ( c u r l − L − s h t t p s : / / d l . k …...

图像基本变换

缩放与裁剪裁剪图像的裁剪&#xff0c;是指将图像的某个区域切割出来。一些常见的应用场景包括&#xff1a;* 感兴趣区域提取* 去除无用信息* 图像增强* 纠偏&#xff1a;去除不规则部分&#xff0c;将图像变得更加整齐事实上&#xff0c;图像裁剪的裁剪通常就是一个numpy矩阵切…...

基于文心一言的底层视觉理解,百度网盘把「猫」换成了「黄色的猫」

随着移动互联网的一路狂飙&#xff0c;手机已经成为人们的新器官。出门不带钥匙可以&#xff0c;不带手机却是万万不可以的。而手机上&#xff0c;小小的摄像头也越来越成为各位「vlogger」的口袋魔方。每天有超过数亿的照片和视频被上传到百度网盘中&#xff0c;这些照片和视频…...

安卓开发的环境配置教程

文章目录事先准备&#xff1a;下载 JDK、Gradle下载安装 Android Studio下载安装 Android SDK下载安装 ADB笔者的环境&#xff1a; Java 17.0.1 Gradle 8.0.1 Android Studio Electric Eel | 2022.1.1 Patch 1 Windows 10 教育版 64位 事先准备&#xff1a;下载 JDK、Gradl…...

【Spring Cloud Alibaba】Spring Cloud Alibaba 搭建教程

文章目录教程适用版本一、简介主要功能组件开源地址二、开始搭建1.项目搭建与依赖管理2.服务注册与发现&#xff08;Nacos安装&#xff09;3.创建服务提供者4.创建服务消费者5.创建服务消费者(Feign)6.添加熔断机制&#xff08;Sentinel&#xff09;7.Sentinel熔断器仪表盘监控…...

关于自动机器学习flaml训练时的一些报错

一、版本背景flaml 1.1.3sciket-learn 0.23.0二、一路报错2.1、SyntaxError: future feature annotations is not definedTraceback (most recent call last):File "C:/Users/dell/Desktop/AI/run.py", line 151, in <module>model.autoMlArgs(queryDf,targe…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法

用神经网络读懂你的“心情”:揭秘情绪识别系统背后的AI魔法 大家好,我是Echo_Wish。最近刷短视频、看直播,有没有发现,越来越多的应用都开始“懂你”了——它们能感知你的情绪,推荐更合适的内容,甚至帮客服识别用户情绪,提升服务体验。这背后,神经网络在悄悄发力,撑起…...

Java中栈的多种实现类详解

Java中栈的多种实现类详解&#xff1a;Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...