编辑距离算法全解析：优化文本处理的关键技术

输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

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

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

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

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

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