【LeetCode 热题 100】72. 编辑距离——（解法一）记忆化搜索

Problem: 72. 编辑距离

整体思路

这段代码旨在解决经典的 “编辑距离” (Edit Distance) 问题，也称为 莱文斯坦距离 (Levenshtein Distance)。问题要求计算将一个字符串 word1 转换为另一个字符串 word2 所需的最少操作次数。允许的操作有三种：插入一个字符、删除一个字符、替换一个字符。

该算法采用的是一种 自顶向下（Top-Down）的动态规划 方法，即 记忆化搜索 (Memoization)。它将两个长字符串的编辑距离问题，分解为它们各种前缀之间的编辑距离子问题，并通过递归解决，同时使用一个二维数组来缓存已解决的子问题的答案，以避免重复计算。

算法的核心逻辑如下：

1. 问题分解与递归关系：

   • 算法的核心思想是比较两个字符串的末尾字符。
   • 我们定义一个函数 dfs(i, j)，其含义是 “word1 的前 i+1 个字符（word1[0...i]）与 word2 的前 j+1 个字符（word2[0...j]）之间的最小编辑距离”。
   • 对于 dfs(i, j)，有两种情况：
     a. 末尾字符相同 (w1[i] == w2[j])：如果两个字符串的最后一个字符相同，那么我们不需要对这两个字符进行任何操作。问题直接简化为计算它们各自去掉末尾字符后的编辑距离，即 dfs(i-1, j-1)。
     b. 末尾字符不同 (w1[i] != w2[j])：如果最后一个字符不同，我们必须执行一次操作才能使它们匹配。有三种选择，我们取其中成本最小的：
     • 替换 (Replace)：将 w1[i] 替换为 w2[j]。操作后末尾字符匹配，问题变为计算 word1[0...i-1] 和 word2[0...j-1] 的距离。成本是 1 + dfs(i-1, j-1)。
     • 删除 (Delete)：删除 w1[i]。问题变为计算 word1[0...i-1] 和 word2[0...j] 的距离。成本是 1 + dfs(i-1, j)。
     • 插入 (Insert)：在 w1 末尾插入 w2[j]。问题变为计算 w1[0...i] 和 w2[0...j-1] 的距离。成本是 1 + dfs(i, j-1)。
       因此，dfs(i, j) = 1 + min(dfs(i-1, j-1), dfs(i-1, j), dfs(i, j-1))。

2. 记忆化 (Memoization)：

   • 纯粹的递归会导致子问题被大量重复计算，效率极低。
   • 算法使用二维 memo 数组存储 dfs(i, j) 的计算结果。在函数开头检查 memo，如果已计算，直接返回结果。

3. 基础情况 (Base Cases)：

   • if (i < 0): word1 为空串。要将其转换成 word2[0...j]，需要 j+1 次插入操作。
   • if (j < 0): word2 为空串。要将 word1[0...i] 转换成空串，需要 i+1 次删除操作。

完整代码

import java.util.Arrays;class Solution {private char[] w1;private char[] w2;private int[][] memo;/*** 计算将 word1 转换成 word2 所使用的最少操作数。* @param word1 第一个单词* @param word2 第二个单词* @return 最小编辑距离*/public int minDistance(String word1, String word2) {w1 = word1.toCharArray();w2 = word2.toCharArray();int m = w1.length;int n = w2.length;// memo: 记忆化数组。memo[i][j] 存储 dfs(i, j) 的结果。memo = new int[m][n];// 初始化 memo 数组为 -1，表示所有子问题都尚未计算。for (int[] row : memo) {Arrays.fill(row, -1);}// 从两个字符串的末尾开始，自顶向下进行递归求解。return dfs(m - 1, n - 1);}/*** 记忆化搜索函数。* @param i      word1 的当前末尾字符索引* @param j      word2 的当前末尾字符索引* @return word1[0...i] 和 word2[0...j] 的最小编辑距离*/private int dfs(int i, int j) {// 基础情况：如果 word1 的前缀为空串if (i < 0) {// 需要 j+1 次插入操作才能变成 word2 的前缀return j + 1;}// 基础情况：如果 word2 的前缀为空串if (j < 0) {// 需要 i+1 次删除操作才能变成空串return i + 1;}// 记忆化检查：如果该子问题已计算过，直接返回。if (memo[i][j] != -1) {return memo[i][j];}// 状态转移：// 如果当前比较的两个字符相同if (w1[i] == w2[j]) {// 无需操作，距离等于它们各自去掉末尾字符后的距离。return memo[i][j] = dfs(i - 1, j - 1);}// 如果字符不同，必须执行一次操作。// 在 插入、删除、替换 三种操作中选择成本最小的一种。// dfs(i, j-1):   对应插入操作// dfs(i-1, j):   对应删除操作// dfs(i-1, j-1): 对应替换操作return memo[i][j] = Math.min(Math.min(dfs(i, j - 1), dfs(i - 1, j)), dfs(i - 1, j - 1)) + 1;}
}

时空复杂度

时间复杂度：O(m * n)

• m 是 word1 的长度，n 是 word2 的长度。

1. 状态数量：由于记忆化的存在，每个状态 (i, j) 只会被实际计算一次。
   • i 的范围是从 0 到 m-1。
   • j 的范围是从 0 到 n-1。
   • 因此，总的状态数量是 m * n。
2. 每个状态的计算时间：在 dfs 函数内部，除了递归调用，其他的操作都是 O(1) 的。

综合分析：
总的时间复杂度等于（状态数量）×（每个状态的计算时间），即 O(m * n)。记忆化将算法从指数级 O(3^(m+n)) 优化到了多项式级。

空间复杂度：O(m * n)

1. 记忆化数组：算法创建了一个 memo 二维数组来存储所有子问题的解。其大小为 m * n。这部分空间占用为 O(m * n)。
2. 递归调用栈：递归的深度也需要考虑。在最坏的情况下，例如 dfs(m-1, n-1) 一路调用 dfs(m-2, n-2) 直到基础情况，递归深度可达 m+n。因此，递归栈所占用的空间是 O(m + n)。

综合分析：
算法所需的总空间是 O(m * n) (用于 memo 数组) + O(m + n) (用于递归栈)。由于 m*n 是主导项，因此最终的空间复杂度为 O(m * n)。