1. 题目

2. 思路

(1) 动态规划

• 题目中给出的三种操作可以简化为以下三种操作：
  1. 向字符串word1插入一个字符；
  2. 向字符串word2插入一个字符；
  3. 修改字符串word1的一个字符。
• dp[i][j]表示使字符串word1的前i个字符和字符串word2的前j个字符相等的最少操作次数。
• 对于前两个操作，状态转移方程为dp[i][j]=dp[i-1][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。
• 最终的dp[i][j]取三种操作的最小值。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int minDistance(String word1, String word2) {char[] c1 = word1.toCharArray();char[] c2 = word2.toCharArray();int n1 = c1.length;int n2 = c2.length;if (n1 * n2 == 0) {return n1 + n2;}int[][] dp = new int[n1 + 1][n2 + 1];for (int i = 0; i <= n1; i++) {dp[i][0] = i;}for (int j = 0; j <= n2; j++) {dp[0][j] = j;}for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (c1[i - 1] == c2[j - 1]) {dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));} else {dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));}}}return dp[n1][n2];}
}