72. Edit Distance
給定兩個字符串 word1 和 word2，返回將 word1 轉換為 word2 所需的最少操作次數。
你可以對一個單詞進行以下三種操作：插入一個字符
刪除一個字符
替換一個字符
範例 1：
輸入：word1 = "horse", word2 = "ros" 輸出：3 解釋：horse -> rorse (用 'r' 替換 'h')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')
Python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# Create a 2D array dp where dp[i][j] represents the minimum number of operations
# to convert word1[0..i-1] to word2[0..j-1]
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize the base cases
for i in range(m + 1):
dp[i][0] = i # Deleting all characters from word1
for j in range(n + 1):
dp[0][j] = j # Inserting all characters of word2
# Fill 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] # Characters match, no extra operation needed
else:
dp[i][j] = min(dp[i - 1][j] + 1, # Delete from word1
dp[i][j - 1] + 1, # Insert into word1
dp[i - 1][j - 1] + 1) # Replace in word1
return dp[m][n]
19.91MB, 109ms
C++
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
// Create a 2D array dp where dp[i][j] represents the minimum number of operations
// to convert word1[0..i-1] to word2[0..j-1]
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// Initialize the base cases
for (int i = 0; i <= m; ++i) {
dp[i][0] = i; // Deleting all characters from word1
}
for (int j = 0; j <= n; ++j) {
dp[0][j] = j; // Inserting all characters of word2
}
// Fill 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]; // Characters match, no extra operation needed
} else {
dp[i][j] = min({dp[i - 1][j] + 1, // Delete from word1
dp[i][j - 1] + 1, // Insert into word1
dp[i - 1][j - 1] + 1}); // Replace in word1
}
}
}
return dp[m][n];
}
};
11.93MB, 5ms
Javascript
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
const m = word1.length;
const n = word2.length;
// Create a 2D array dp where dp[i][j] represents the minimum number of operations
// to convert word1[0..i-1] to word2[0..j-1]
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// Initialize the base cases
for (let i = 0; i <= m; i++) {
dp[i][0] = i; // Deleting all characters from word1
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j; // Inserting all characters of word2
}
// Fill the dp array
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // Characters match, no extra operation needed
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Delete from word1
dp[i][j - 1] + 1, // Insert into word1
dp[i - 1][j - 1] + 1 // Replace in word1
);
}
}
}
return dp[m][n];
};
55.5MB, 95ms
