leetcode -编辑距离

为了求解将 `word1` 转换成 `word2` 所需的最少操作数，可以使用动态规划。以下是详细的解决方案：

 

### 方法思路

1. **定义状态**  

   `dp[i][j]` 表示将 `word1` 的前 `i` 个字符转换成 `word2` 的前 `j` 个字符所需的最少操作数。

 

2. **状态转移方程**  

   - 如果 `word1[i-1] == word2[j-1]`（字符相同），直接继承前一步的结果：  

     `dp[i][j] = dp[i-1][j-1]`。

   - 如果字符不同，选择以下三种操作中的最小值：  

     - **替换**：`dp[i-1][j-1] + 1`（替换当前字符）。  

     - **删除**：`dp[i-1][j] + 1`（删除 `word1` 的第 `i` 个字符）。  

     - **插入**：`dp[i][j-1] + 1`（在 `word1` 末尾插入字符以匹配 `word2` 的第 `j` 个字符）。  

 

3. **初始化**  

   - `dp[i][0] = i`：将 `word1` 的前 `i` 个字符删除为空字符串需要 `i` 次操作。  

   - `dp[0][j] = j`：将空字符串插入为 `word2` 的前 `j` 个字符需要 `j` 次操作。

 

### 解决代码

```java

import java.util.Scanner;

 

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String word1 = sc.nextLine();

        String word2 = sc.nextLine();

        System.out.println(minDistance(word1, word2));

    }

 

    public static 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] = Math.min(

                        dp[i - 1][j - 1], // 替换

                        Math.min(dp[i - 1][j], dp[i][j - 1]) // 删除或插入

                    ) + 1;

                }

            }

        }

 

        return dp[m][n];

    }

}

```

 

### 代码解释

1. **初始化**  

   处理边界情况，当其中一个字符串为空时，操作数为另一个字符串的长度。

 

2. **动态规划填充**  

   遍历所有可能的子问题，根据字符是否相同选择直接继承或取三种操作的最小值。

 

3. **时间复杂度**  

   \(O(m \times n)\)，其中 \(m\) 和 \(n\) 分别为 `word1` 和 `word2` 的长度。

 

该方法通过动态规划高效地计算了最小编辑距离，覆盖了所有可能的操作情况。