有哪些做分析图用的网站,网络公关名词解释,抖音小程序模板,品牌推广与传播递归暴力解法
递归方法的基本思想是考虑最后一个字符的操作#xff0c;然后根据这些操作递归处理子问题。
递归函数定义#xff1a;定义一个递归函数 minDistance(i, j)#xff0c;表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。
递归终止条件…
递归暴力解法
递归方法的基本思想是考虑最后一个字符的操作然后根据这些操作递归处理子问题。
递归函数定义定义一个递归函数 minDistance(i, j)表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。
递归终止条件
如果 i 0意味着 word1 为空此时将 word1 转换成 word2 的前 j 个字符就需要 j 次插入操作。如果 j 0意味着 word2 为空此时将 word1 的前 i 个字符转换成空字符串需要 i 次删除操作。
递归转移方程
如果 word1[i-1] word2[j-1]则当前两个字符相等不需要操作所以 minDistance(i, j) minDistance(i-1, j-1)。如果不相等则可以进行插入、删除或替换操作转移方程为 插入minDistance(i, j) minDistance(i, j-1) 1删除minDistance(i, j) minDistance(i-1, j) 1替换minDistance(i, j) minDistance(i-1, j-1) 1取三者的最小值。
代码如下
public class Solution {// 主方法用于外部调用传入两个字符串public int minDistance(String word1, String word2) {// 调用递归助手函数初始化i和j为字符串的长度从字符串尾部开始比较return minDistanceHelper(word1, word2, word1.length(), word2.length());}// 递归助手函数用于计算两个字符串的最小编辑距离private int minDistanceHelper(String word1, String word2, int m, int n) {// 如果第一个字符串为空则转换的代价是第二个字符串的长度即插入n次if (m 0) return n;// 如果第二个字符串为空则转换的代价是第一个字符串的长度即删除m次if (n 0) return m;// 如果两个字符串的当前字符相等则不需要操作递归考虑前一个字符if (word1.charAt(m - 1) word2.charAt(n - 1)) {return minDistanceHelper(word1, word2, m - 1, n - 1);}// 计算插入操作的代价将word2的第n个字符插入到word1的末尾然后继续处理剩余的字符串int insert minDistanceHelper(word1, word2, m, n - 1) 1;// 计算删除操作的代价删除word1的第m个字符然后继续处理剩余的字符串int delete minDistanceHelper(word1, word2, m - 1, n) 1;// 计算替换操作的代价将word1的第m个字符替换为word2的第n个字符然后继续处理剩余的字符串int replace minDistanceHelper(word1, word2, m - 1, n - 1) 1;// 返回三种操作中的最小值即为到当前位置为止的最小编辑距离return Math.min(Math.min(insert, delete), replace);}
}但是重复计算效率很慢改成动态规划
动态规划方法
动态规划方法的核心思想是使用一个二维数组 dp 来存储中间结果其中 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数。通过填充这个数组我们可以逐步构建出从一个空字符串到完整 word2再从完整 word1 到 word2 的转换路径。
初始化
dp[0][j]将空字符串转换为 word2 的前 j 个字符需要 j 次插入操作。dp[i][0]将 word1 的前 i 个字符转换为空字符串需要 i 次删除操作。
状态转移方程
如果 word1[i-1] word2[j-1]则 dp[i][j] dp[i-1][j-1]因为最后一个字符已经匹配不需要额外操作。如果 word1[i-1] ! word2[j-1]则可以从以下三个可能的操作中选择最小成本的 插入dp[i][j] dp[i][j-1] 1删除dp[i][j] dp[i-1][j] 1替换dp[i][j] dp[i-1][j-1] 1
代码如下
public class Solution {public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int[][] dp new int[m 1][n 1];// 初始化dp数组for (int i 0; i m; i) {dp[i][0] i; // 从word1的i字符变为空字符串}for (int j 0; j n; j) {dp[0][j] j; // 从空字符串变为word2的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] Math.min(Math.min(dp[i-1][j] 1, dp[i][j-1] 1), dp[i-1][j-1] 1);}}}return dp[m][n];}
}
