题目描述 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。 示例 思路 其实这道题的思路和最长公共子序列的思路一致,本题让我们求word1 和 word2 相同所需的最小步数,也就是说求word1和word2变成它两的最长公共子序列的步数,那么我们可以求出它两的最长公共子序列,然后,分别用它们各自的长度减去子序列长度就是所求。 代码如下 public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m + 1][n + 1]; for(int i = 1;i < dp.length;i++){ for(int j = 1;j < dp[0].length;j++){ if(word1.charAt(i - 1) == word2.charAt(j - 1)){ dp[i][j] = 1 + dp[i - 1][j - 1]; }else{ dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]); } } } return m + n - 2 * dp[m][n]; }
收录于话题
相关信息
你可能还喜欢
热门推荐信息
2023最新AI创作系统ChatGPT网站源码+Midjourney绘画+支持GPT-4-Turbo模型+即将支持TSS语音对话功能模块
By白云如幻
一、AI创作系统 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型+国内AI全模型。本期针对源码系统整体测试下来非常完 ...
初识Dockerfile
Byqq_58647543
Dockerfile简介 从之前的学习中我们可以了解到:镜像的定制实际上就是定制每一层所添加的配置、文件。那么如果我们可以把每一层修改、安装、构建、操作的命令都写入一个脚本,用这个脚本来构建、定制镜像 ...
C#中 怎么检测Tcp网线断开?
By望天hous
在 C# 中,如果使用 TcpClient 或 TcpListener 这样的套接字进行通信,并且网络连接断开,不发送心跳是无法立即检测到断开的。这是因为 TCP 协议本身没有内置的机制来检测连接是否 ...
OpenCvSharpSlim画中文
By乱蜂朝王
github地址:https://github.com/AvenSun/OpenCvSharpSlim Slim Build of OpenCvSharp OpenCvSharpSlim This p ...
Ubuntu22.04 server版本关闭DHCP,手动设置ip
By清浊-
在Ubuntu 22.04 中,网络配置已迁移到 Netplan,因此可以使用 Netplan 配置文件来手动设置 IP 地址并关闭 DHCP。 以下是在 Ubuntu 22.04 上手动设置 IP ...