作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
这是力扣72题：编辑距离
题目描述
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
输入格式
- word1：一个字符串。
- word2：一个字符串。
输出格式
- 返回将
word1转换成word2的最小操作数。
示例
示例 1
输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2
输入: word1 = "intention", word2 = "execution" 输出: 5 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
方法一：动态规划
解题步骤
- 定义状态数组：
dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少操作。 - 初始化边界：初始化
dp数组的第一行和第一列，分别表示空字符串到任意长度字符串的转换。 - 状态转移方程：
- 如果
word1[i-1] == word2[j-1]，则dp[i][j] = dp[i-1][j-1]； - 否则，取插入、删除、替换操作的最小值加一，即
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
- 计算最终结果：返回
dp[m][n]。
完整的规范代码
def minDistance(word1, word2): """ 使用动态规划解决编辑距离问题 :param word1: str, 第一个单词 :param word2: str, 第二个单词 :return: int, 最少操作数 """ m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): dp[i][0] = i for j in range(1, n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 return dp[m][n] # 示例调用 print(minDistance("horse", "ros")) # 输出: 3 print(minDistance("intention", "execution")) # 输出: 5
算法分析
- 时间复杂度：(O(m * n))，其中
m和n分别是两个字符串的长度。 - 空间复杂度：(O(m * n))，用于存储
dp表。
方法二：空间优化的动态规划
解题步骤
- 使用滚动数组：使用两行（当前行和前一行）或一行（滚动更新）来减少空间复杂度。
- 状态转移：更新
dp数组时，只依赖于当前行的前一个元素和上一行的元素，因此可以用一维数组滚动更新。
完整的规范代码
def minDistance(word1, word2): """ 使用空间优化的动态规划解决编辑距离问题 :param word1: str, 第一个单词 :param word2: str, 第二个单词 :return: int, 最少操作数 """ if len(word1) < len(word2): word1, word2 = word2, word1 m, n = len(word1), len(word2) previous, current = list(range(n + 1)), [0] * (n + 1) for i in range(1, m + 1): current[0] = i for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: current[j] = previous[j - 1] else: current[j] = min(previous[j - 1], previous[j], current[j - 1]) + 1 previous, current = current, previous return previous[n] # 示例调用 print(minDistance("horse", "ros")) # 输出: 3 print(minDistance("intention", "execution")) # 输出: 5
算法分析
- 时间复杂度：(O(m * n))，与完整的动态规划相同。
- 空间复杂度：(O(min(m, n)))，只使用两个长度为
n + 1的数组。
方法三：递归加记忆化
解题步骤
- 定义递归函数：定义一个递归函数来计算
word1[0...i]和word2[0...j]的编辑距离。 - 记忆化存储：使用一个二维数组来存储已计算的结果，避免重复计算。
- 递归计算：基于给定的操作计算最小编辑距离。
完整的规范代码
def minDistance(word1, word2): """ 使用递归加记忆化解决编辑距离问题 :param word1: str, 第一个单词 :param word2: str, 第二个单词 :return: int, 最少操作数 """ memo = {} def dp(i, j): if (i, j) in memo: return memo[(i, j)] if i == 0: return j if j == 0: return i if word1[i - 1] == word2[j - 1]: ans = dp(i - 1, j - 1) else: ans = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1 memo[(i, j)] = ans return ans return dp(len(word1), len(word2)) # 示例调用 print(minDistance("horse", "ros")) # 输出: 3 print(minDistance("intention", "execution")) # 输出: 5
算法分析
- 时间复杂度：(O(m * n))，递归处理每对索引一次。
- 空间复杂度：(O(m * n))，用于存储递归调用栈和记忆化结果。
方法四：迭代加记忆化
解题步骤
- 初始化：建立一个二维数组用于记忆化存储。
- 基本情况填充：填充数组的基本情况（一个字符串为空的情况）。
- 迭代计算：使用之前填充的结果迭代计算整个
dp表。
完整的规范代码
def minDistance(word1, word2): """ 使用迭代加记忆化解决编辑距离问题 :param word1: str, 第一个单词 :param word2: str, 第二个单词 :return: int, 最少操作数 """ m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 return dp[m][n] # 示例调用 print(minDistance("horse", "ros")) # 输出: 3 print(minDistance("intention", "execution")) # 输出: 5
方法五：基于编辑操作的动态规划
解题步骤
- 分析编辑操作：将编辑操作细分为插入、删除、替换，并为每种操作定义独立的逻辑。
- 逐步构建解决方案：基于以上操作，构建一个解决方案，逐步填充
dp表。
完整的规范代码
def minDistance(word1, word2): """ 基于编辑操作的动态规划解决编辑距离问题 :param word1: str, 第一个单词 :param word2: str, 第二个单词 :return: int, 最少操作数 """ m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: insert_op = dp[i][j - 1] delete_op = dp[i - 1][j] replace_op = dp[i - 1][j - 1] dp[i][j] = min(insert_op, delete_op, replace_op) + 1 return dp[m][n] # 示例调用 print(minDistance("horse", "ros")) # 输出: 3 print(minDistance("intention", "execution")) # 输出: 5
不同算法的优劣势对比
| 特征 | 方法一：动态规划 | 方法二：空间优化DP | 方法三：递归加记忆化 | 方法四：迭代加记忆化 | 方法五：基于编辑操作DP |
| 时间复杂度 | (O(m * n)) | (O(m * n)) | (O(m * n)) | (O(m * n)) | (O(m * n)) |
| 空间复杂度 | (O(m * n)) | (O(min(m, n))) | (O(m * n)) | (O(m * n)) | (O(m * n)) |
| 优势 | 易于理解和实现 | 空间复杂度较低 | 避免重复计算，提高效率 | 适合大规模数据处理 | 直观反映不同编辑操作 |
| 劣势 | 空间占用大 | 代码稍复杂 | 空间占用大 | 空间占用大 | 实现较为复杂 |
应用示例
自然语言处理：在自然语言处理领域，编辑距离用来衡量两个词语之间的相似度，常用于拼写检查、语音识别系统等领域。
数据库记录匹配：在数据清洗过程中，编辑距离可以帮助识别和合并重复的记录，例如在客户数据库中识别重复的客户名称。
生物信息学：在生物信息学中，编辑距离用于比较基因序列的相似性，对于基因编辑和比较具有重要的应用价值。
欢迎关注微信公众号 数据分析螺丝钉
