网站建设小白到精通需要,比较好看的wordpress主题,花里胡哨的网站,品牌网站建设3a小蝌蚪【问题描述】 给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1#xff1a;
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为…【问题描述】 给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为 ea 第二步将 eat 变为 ea这个问题可以使用动态规划来解决。我们可以构建一个二维数组 dp其中 dp[i][j] 表示将 word1 的前 i 个字符变成 word2 的前 j 个字符所需的最小步数。
算法的核心思想是根据不同的情况来计算 dp[i][j]
如果 word1.charAt(i - 1) 等于 word2.charAt(j - 1)说明当前字符是相同的无需删除因此可以直接继承上一个状态的步数即 dp[i][j] dp[i - 1][j - 1]。否则我们可以考虑删除 word1 的第 i 个字符或删除 word2 的第 j 个字符取两者中步数较小的即 dp[i][j] 1 Math.min(dp[i - 1][j], dp[i][j - 1])。
最终dp[word1.length()][word2.length()] 就是将整个 word1 变成 word2 所需的最小步数。 【Java代码】
public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int[][] dp new int[m 1][n 1];// 初始化边界情况// 如果其中一个为空串那么另一个字符串必须删除所有字符for (int i 0; i m; i) {dp[i][0] i;}for (int j 0; j n; j) {dp[0][j] j;}// 计算 dp 数组for (int i 1; i m; i) {for (int j 1; j n; j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] 1 Math.min(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}
