最少前缀操作问题--感受不到动态规划,怎么办怎么办

news/2024/12/17 1:02:05/

题目:

标签:动态规划(应该是双指针的,不理解)

小U和小R有两个字符串,分别是S和T,现在小U需要通过对S进行若干次操作,使其变成T的一个前缀。操作可以是修改S的某一个字符,或者删除S末尾的字符。现在你需要帮助小U计算出,最少需要多少次操作才能让S变成T的前缀。


测试样例

样例1:

输入:S = "aba", T = "abb"
输出:1

样例2:

输入:S = "abcd", T = "efg"
输出:4

样例3:

输入:S = "xyz", T = "xy"
输出:1

样例4:

输入:S = "hello", T = "helloworld"
输出:0

样例5:

输入:S = "same", T = "same"
输出:0


不行,感觉我的脑子废了,第一遍是用动态规划解决该问题,但是!wrong!参考了下那个Al的想法是了下,感觉我的智商堪忧,这个怎么也不是动态规划的题解。

java">public class Main {public static int solution(String S, String T) {//最少的前缀操作次数,说实话,做了这道题目感受不到一点动态规划的感觉int deleteCount = 0;if(S.length() > T.length()){deleteCount = S.length() -  T.length();}int i = 0;int j = 0;int count = 0;while(i < Math.min(S.length(),T.length())){if(S.charAt(i) != T.charAt(j)){count ++;}i++;j++;}return count + deleteCount;}public static void main(String[] args) {System.out.println(solution("aba", "abb") == 1);System.out.println(solution("abcd", "efg") == 4);System.out.println(solution("xyz", "xy") == 1);System.out.println(solution("hello", "helloworld") == 0);System.out.println(solution("same", "same") == 0);}
}

http://www.ppmy.cn/news/1555722.html

相关文章

深圳国威HB1910数字IP程控交换机 generate.php 远程命令执行漏洞复现

0x01 产品描述: 深圳国威主营国威模拟、数字、IP 交换机、语音网关、IP 电话机及各种电话机。深圳国威电子有限公司HB1910是一款功能强大的网络通信设备,适用于各种企业通信需求。 0x02 漏洞描述: 深圳国威电子有限公司HB1910数字IP程控交换机generate.php存在远程命令执行…

【愚公系列】《微信小程序与云开发从入门到实践》002-如何设计一款小程序

标题详情作者简介愚公搬代码头衔华为云特约编辑&#xff0c;华为云云享专家&#xff0c;华为开发者专家&#xff0c;华为产品云测专家&#xff0c;CSDN博客专家&#xff0c;CSDN商业化专家&#xff0c;阿里云专家博主&#xff0c;阿里云签约作者&#xff0c;腾讯云优秀博主&…

汽车保养系统+ssm

摘 要 由于APP软件在开发以及运营上面所需成本较高&#xff0c;而用户手机需要安装各种APP软件&#xff0c;因此占用用户过多的手机存储空间&#xff0c;导致用户手机运行缓慢&#xff0c;体验度比较差&#xff0c;进而导致用户会卸载非必要的APP&#xff0c;倒逼管理者必须改…

js 应用的几大原则 及 应用实例

文章目录 js 应用的几大原则vue3 中原则应用体现react 原则应用体现 js 应用的几大原则 单一职责原则&#xff08;SRP&#xff09; 解释&#xff1a;一个函数或者一个对象应该只有一个职责。这意味着函数应该只做一件事情并且把它做好。例如&#xff0c;一个函数只负责计算两个…

JAVA爬虫获取1688关键词接口

以下是使用Java爬虫获取1688关键词接口的详细步骤和示例代码&#xff1a; 一、获取API接口访问权限 要使用1688关键词接口&#xff0c;首先需要获取API的使用权限&#xff0c;并了解接口规范。以下是获取API接口的详细步骤&#xff1a; 注册账号&#xff1a;在1688平台注册一…

npm、yarn、pnpm三者的异同

这个表格将会说明一切&#xff1a; 特性npmyarnpnpm依赖管理方式扁平化管理&#xff0c;嵌套依赖树&#xff0c;可能重复安装扁平化管理喝符号链接&#xff0c;同版本只能安装一次基于硬链接喝符号链接的内容寻址存储安装速度最慢中等(并行安装)最快(得益于硬链接的复用)磁盘空…

舌头分割数据集labelme格式2557张1类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)&#xff1a;2557 标注数量(json文件个数)&#xff1a;2557 标注类别数&#xff1a;1 标注类别名称:["tongue"] 每个类别标注的框数&#xff1…

CSS文本属性

字间距 letter-spacing需要为合法的尺寸单位可以设置为负值&#xff0c;此时字间间距会比正常值小并重叠起来可以为10px、-4px、normal&#xff08;正常字间距&#xff09; div{letter-spacing: 10px;}行高 指的是行与行之间的间距&#xff0c;是一行的高度&#xff0c;不是行…