【经典算法】LeetCode 72. 编辑距离(Java/C/Python3/Go实现含注释说明,中等)

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

原题：LeetCode 72

思路及实现

方式一：动态规划

思路

使用二维数组 dp 来保存子问题的解，其中 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。

• 当 word1[i-1] == word2[j-1] 时，不需要进行操作，dp[i][j] = dp[i-1][j-1]。
• 当 word1[i-1] != word2[j-1] 时，可以选择插入、删除或替换操作，取这三种操作的最小值加1，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

代码实现

Java版本

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    // 创建一个二维数组dp
    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] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    
    return dp[m][n];
}

说明：Java版本使用了二维数组dp来保存中间结果，并通过循环填充该数组。

C语言版本

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minDistance(char *word1, char *word2) {
    int m = strlen(word1);
    int n = strlen(word2);
    
    // 创建一个二维数组dp
    int dp[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[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + fmin(fmin(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

说明：C语言版本与Java版本类似，但使用了fmin函数来取最小值。

Python3版本

def minDistance(word1: str, word2: str) -> int:
    m, n =len(word1), len(word2)
    
    # 创建一个二维数组dp
    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
    
    # 填充dp数组
    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] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

说明：Python3版本使用列表推导式创建二维数组，并使用min函数来取最小值。

Golang版本

package main

import (
	"fmt"
	"math"
)

func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	
	// 创建一个二维数组dp
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	
	// 初始化第一行和第一列
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	
	// 填充dp数组
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = 1 + int(math.Min(float64(dp[i-1][j-1]), math.Min(float64(dp[i-1][j]), float64(dp[i][j-1]))))
			}
		}
	}
	
	return dp[m][n]
}

func main() {
	word1 := "horse"
	word2 := "ros"
	fmt.Println(minDistance(word1, word2)) // 输出: 3
}

说明：Golang版本使用make函数创建二维切片，并使用math.Min函数来取最小值。

复杂度分析

• 时间复杂度：O(m * n)，其中m和n分别是两个单词的长度。因为我们需要遍历两个单词的所有字符。
• 空间复杂度：O(m * n)，用于保存子问题的解。

总结

相似题目