当前位置: 首页 > 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…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...