编辑距离

题目要求

给定两个字符串 word1 和 word2，要求通过以下三种操作将 word1 转换为 word2：

插入一个字符
删除一个字符
替换一个字符

目标是找出并返回将 word1 转换成 word2 所需的最少操作次数。

解题思路

这个问题是一个经典的动态规划问题，通常被称为编辑距离问题（Edit Distance）。解决这个问题的思路可以分为以下几个步骤：

初始化二维数组 dp：创建一个 (m+1) x (n+1) 的二维数组 dp，其中 m 和 n 分别是 word1 和 word2 的长度。dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。初始化 dp[0][0] 为 0，dp[i][0] 为 i（即删除操作），dp[0][j] 为 j（即插入操作）。
填充 dp 数组：遍历 word1 和 word2，对于每一对字符 word1[i] 和 word2[j]，计算 dp[i][j]。有三种情况：
- 如果 word1[i] 等于 word2[j]，则 dp[i][j] 应该等于 dp[i-1][j-1]（无需操作）。
- 如果 word1[i] 不等于 word2[j]，则 dp[i][j] 应该是以下三个值中的最小值加一：
  - dp[i-1][j]（word1 删除一个字符后与 word2 比较）
  - dp[i][j-1]（word1 插入一个字符后与 word2 比较）
  - dp[i-1][j-1]（word1 替换一个字符后与 word2 比较）
返回结果：经过上述步骤后，dp[m][n] 就是将 word1 转换成 word2 所需的最少操作数。

通过这种方法，我们可以确保每一步都是基于之前计算的最优解，从而确保最终结果是全局最优的。

Golang 版本

package main

import (
	"fmt"
	"math"
)

// minDistance calculates the minimum number of operations required to convert word1 to word2
func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	// Create a DP table to store results of subproblems
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// Initialize the DP table
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}

	// Fill the DP table
	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 + min(
					dp[i-1][j],   // Delete
					dp[i][j-1],   // Insert
					dp[i-1][j-1], // Replace
				)
			}
		}
	}

	// The result is in dp[m][n]
	return dp[m][n]
}

// min returns the minimum of three integers
func min(a, b, c int) int {
	return int(math.Min(float64(a), math.Min(float64(b), float64(c))))
}

func main() {
	word1 := "intention"
	word2 := "execution"
	fmt.Println("Minimum operations required to convert:", minDistance(word1, word2))
}

这段代码定义了一个 minDistance 函数，它接受两个字符串 word1 和 word2 并返回将 word1 转换为 word2 所需的最少操作数。它使用动态规划的方法来填充一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。最后，dp[m][n] 就是答案。主函数 main 提供了一个示例调用。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

// Function to find the minimum number of operations to convert word1 to word2
int minDistance(std::string word1, std::string word2) {
    int m = word1.length(), n = word2.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    // Initialize the dp array
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    // Compute the dp array
    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 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }

    // The answer is in dp[m][n]
    return dp[m][n];
}

int main() {
    std::string word1 = "intention";
    std::string word2 = "execution";
    std::cout << "Minimum operations required to convert: " << minDistance(word1, word2) << std::endl;
    return 0;
}

这段 C++代码实现了一个 minDistance 函数，它计算并返回将字符串 word1 转换为字符串 word2 所需的最少操作数。它使用动态规划方法，通过构建一个二维的 dp 数组来存储中间结果。dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。最终结果存储在 dp[m][n] 中。主函数 main 提供了一个示例用于演示如何调用 minDistance 函数。

Python 版本

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initialize the dp array
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # Compute the dp array
    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],    # Delete
                                   dp[i][j - 1],    # Insert
                                   dp[i - 1][j - 1]) # Replace

    # The answer is in dp[m][n]
    return dp[m][n]

# Example usage
word1 = "intention"
word2 = "execution"
print("Minimum operations required to convert:", minDistance(word1, word2))

这段 Python 代码定义了一个 minDistance 函数，它接受两个字符串 word1 和 word2 并返回将 word1 转换为 word2 所需的最少操作数。它使用动态规划的方法来填充一个二维列表 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。最后，dp[m][n] 就是答案。代码的最后部分提供了一个示例调用。

Java 版本

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Initialize the dp array
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // Compute the dp array
        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], // Delete
                                    Math.min(dp[i][j - 1], // Insert
                                             dp[i - 1][j - 1])); // Replace
                }
            }
        }

        // The answer is in dp[m][n]
        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String word1 = "intention";
        String word2 = "execution";
        System.out.println("Minimum operations required to convert: " + solution.minDistance(word1, word2));
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含一个 minDistance 方法，用于计算将一个字符串转换为另一个字符串所需的最少操作数。它使用动态规划方法，通过构建一个二维数组 dp 来存储中间结果。dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。main 方法提供了一个示例，展示了如何使用 minDistance 方法。

Rust 版本

fn min_distance(word1: &str, word2: &str) -> i32 {
    let m = word1.len();
    let n = word2.len();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    // Initialize the dp array
    for i in 0..=m {
        dp[i][0] = i as i32;
    }
    for j in 0..=n {
        dp[0][j] = j as i32;
    }

    let word1_bytes = word1.as_bytes();
    let word2_bytes = word2.as_bytes();

    // Compute the dp array
    for i in 1..=m {
        for j in 1..=n {
            if word1_bytes[i - 1] == word2_bytes[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::cmp::min(
                    std::cmp::min(dp[i - 1][j], dp[i][j - 1]),
                    dp[i - 1][j - 1],
                );
            }
        }
    }

    // The answer is in dp[m][n]
    dp[m][n]
}

fn main() {
    let word1 = "intention";
    let word2 = "execution";
    println!("Minimum operations required to convert: {}", min_distance(word1, word2));
}

这段 Rust 代码定义了一个 min_distance 函数，它接受两个字符串切片 word1 和 word2 并返回一个 i32 类型的值，表示将 word1 转换为 word2 所需的最少操作数。它使用动态规划的方法来填充一个二维向量 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。最后，dp[m][n] 就是答案。main 函数提供了一个示例调用。

总结

上述代码片段展示了如何使用动态规划（Dynamic Programming, DP）算法来解决字符串编辑距离问题。这个问题要求我们找出将一个字符串（word1）转换成另一个字符串（word2）所需的最小操作次数，其中操作包括插入、删除和替换字符。

解决方案的核心思想是创建一个二维数组（在 Rust 中是一个向量的向量），记为 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作次数。数组的大小是 (m+1) x (n+1)，其中 m 和 n 分别是 word1 和 word2 的长度。

初始化步骤如下：

dp[0][0] 初始化为 0，因为空字符串转换成空字符串不需要任何操作。
dp[i][0] 初始化为 i，因为将长度为 i 的字符串转换成空字符串需要 i 次删除操作。
dp[0][j] 初始化为 j，因为将空字符串转换成长度为 j 的字符串需要 j 次插入操作。

填充 dp 数组的过程遵循以下规则：

如果 word1[i - 1] 等于 word2[j - 1]，则 dp[i][j] 等于 dp[i - 1][j - 1]，因为当前字符已经匹配，不需要额外操作。
如果不相等，则 dp[i][j] 等于以下三个值中的最小值加一：
- dp[i - 1][j]：从 word1 删除一个字符后的最小操作数。
- dp[i][j - 1]：在 word1 中插入一个字符后的最小操作数。
- dp[i - 1][j - 1]：替换 word1 中的一个字符后的最小操作数。

最终，dp[m][n] 就是将 word1 转换成 word2 所需的最小操作次数。这种方法确保了所有可能的字符串操作序列都被考虑到，并且找到了最优解。

hot-100