leetcode72：编辑距离

题目链接

leetcode

题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：

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

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    状态表示：
        f[i][j] 是将 A[1, i] 变成 B[1, j] 操作的最少次数
    状态计算：
        f[i][j] = min(操作1, 操作2, 操作3)
                = min(插入，删除，替换)
                = min(f[i - 1][j] + 1,
                      f[i][j - 1] + 1,
                      f[i - 1][j - 1] + 0 (A[i] == B[j]) 或 1 (A[i] != B[j]))

    时间复杂度：O(mn)
        其中 m 和 n 分别是两个字符串的长度。
    空间复杂度：O(mn)
        存储状态数组 f[i][j] 需要的空间为 O(mn)。
*/
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        word1 = ' ' + word1, word2 = ' ' + word2;

        int f[m + 1][n + 1];
        f[0][0] = 0;
        for (int i = 1; i <= m; i ++) {
            f[i][0] = i; // 删除
        }
        for (int j = 1; j <= n; j ++) {
            f[0][j] = j; // 插入
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                int cost = (word1[i] == word2[j] ? 0 : 1);
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + cost);
            }
        }

        return f[m][n];
    }
};

/*
    思路同上
    
    时间复杂度：O(mn)
    空间复杂度：O(mn)
*/
class Solution_1 {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        word1 = ' ' + word1, word2 = ' ' + word2;

        int f[m + 1][n + 1];
        f[0][0] = 0;
        for (int i = 1; i <= m; i ++) {
            f[i][0] = i; // 删除
        }
        for (int j = 1; j <= n; j ++) {
            f[0][j] = j; // 插入
        }
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (word1[i] == word2[j]) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    int insertCost = f[i - 1][j] + 1;
                    int deleteCost = f[i][j - 1] + 1;
                    int replaceCost = f[i - 1][j - 1] + 1;
                    f[i][j] = min(min(insertCost, deleteCost), replaceCost);
                }
            }
        }

        return f[m][n];
    }
};

int main() {
    Solution solution;
    
    // 测试用例1
    string word1 = "horse";
    string word2 = "ros";
    cout << "Input: word1 = " << word1 << ", word2 = " << word2 << endl;
    cout << "Output: " << solution.minDistance(word1, word2) << endl;

    // 测试用例2
    word1 = "intention";
    word2 = "execution";
    cout << "Input: word1 = " << word1 << ", word2 = " << word2 << endl;
    cout << "Output: " << solution.minDistance(word1, word2) << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   动态规划：
       使用二维数组 dp，其中 dp[i][j] 表示将 word1[:i] 转换为 word2[:j] 的最小操作次数。
       初始化边界条件：将一个字符串转换为空字符串的操作次数等于其长度。
   状态转移方程：
       如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]。
       否则，dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)。
   边界条件：
       如果 word1 或 word2 为空，返回另一个字符串的长度。

   时间复杂度：O(mn)
       遍历两个字符串的每个字符，时间复杂度为 O(mn)，其中 m 和 n 分别是两个字符串的长度。
   空间复杂度：O(mn)
       使用了一个大小为 (m+1)*(n+1) 的二维数组 dp，空间复杂度为 O(mn)。
*/
// minDistance 返回将 word1 转换为 word2 的最小操作次数
func minDistance(word1, word2 string) int {
	m, n := len(word1), len(word2)
	if m == 0 {
		return n
	}
	if n == 0 {
		return m
	}

	// dp[i][j] 表示 word1[:i] 转换为 word2[:j] 的最小操作次数
	dp := make([][]int, m + 1)
	for i := range dp {
		dp[i] = make([]int, n + 1)
		dp[i][0] = i // 初始化：将 word1[:i] 转换为空字符串的操作次数
	}
	for j := 0; j <= n; j ++ {
		dp[0][j] = j // 初始化：将空字符串转换为 word2[:j] 的操作次数
	}

	// 动态规划填表
	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] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
			}
		}
	}

	return dp[m][n]
}

func main() {
	// 测试用例
	testCases := []struct {
		word1    string
		word2    string
		expected int
	}{
		{
			word1:    "horse",
			word2:    "ros",
			expected: 3,
		},
		{
			word1:    "intention",
			word2:    "execution",
			expected: 5,
		},
	}

	for i, tc := range testCases {
		result := minDistance(tc.word1, tc.word2)
		fmt.Printf("Test Case %d, Input: word1 = %q, word2 = %q\n", i+1, tc.word1, tc.word2)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}