class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[0] * (n + 1) for i 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, c1 in enumerate(word1):
for j, c2 in enumerate(word2):
if c1 == c2:
dp[i + 1][j + 1] = dp[i][j]
else:
dp[i + 1][j + 1] = min(dp[i][j], min(dp[i + 1][j], dp[i][j + 1])) + 1
return dp[m][n]
/*
* @lc app=leetcode id=72 lang=cpp
*
* [72] Edit Distance
*
* https://leetcode.com/problems/edit-distance/description/
*
* algorithms
* Hard (39.09%)
* Likes: 2434
* Dislikes: 37
* Total Accepted: 193.6K
* Total Submissions: 493.5K
* Testcase Example: '"horse"\n"ros"'
*
* Given two words word1 and word2, find the minimum number of operations
* required to convert word1 to word2.
*
* You have the following 3 operations permitted on a word:
*
*
* Insert a character
* Delete a character
* Replace a character
*
*
* Example 1:
*
*
* Input: word1 = "horse", word2 = "ros"
* Output: 3
* Explanation:
* horse -> rorse (replace 'h' with 'r')
* rorse -> rose (remove 'r')
* rose -> ros (remove 'e')
*
*
* Example 2:
*
*
* Input: word1 = "intention", word2 = "execution"
* Output: 5
* Explanation:
* intention -> inention (remove 't')
* inention -> enention (replace 'i' with 'e')
* enention -> exention (replace 'n' with 'x')
* exention -> exection (replace 'n' with 'c')
* exection -> execution (insert 'u')
*
*
*/
class Solution
{
public:
int minDistance(string word1, string word2)
{
const int M = word1.size(), N = word2.size();
vector<vector<int>> dp(M + 1, vector<int>(N + 1));
for (int i = 1; i <= M; ++i)
dp[i][0] = i;
for (int j = 1; j <= N; ++j)
dp[0][j] = j;
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] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[M][N];
}
};