Top Interview 150 P72 Edit Distance

---

Timeline

Timeline

2025-12-16

init

Dynamic Programming

---

Problem:

P72 Edit Distance

https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150

This problem is similar to the longest common subsequence:

Let $dp[i][j]$ denote the minimum number of operations required to convert the first i characters of word1 to the first j characters of word2.

• Initialization:
  • word1[0..=i]becoming an empty string requires i operations, so $dp[i][0] = i$
  • Converting an empty string to word2[0…=j] requires j operations, so$dp[0][j] = j$
• Fordp[i][j], $i,j \ge 1$, we have:
  • ifword[i-1]==word[j-1], then no operation is needed,$dp[i][j]=dp[i-1]dp[j-1]$
  • otherwise $dp[i][j] = min( dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] ) + 1$
    • $dp[i-1][j]+1$ , meaning deletionword1[i-1]
    • $dp[i][j-1]+1$ , meaning insertionword2[j-1]
    • $dp[i-1][j-1]+1$ , meaning replacementword1[i-1]isword2[j-1]

#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::vector;

class Solution {
    public:
        int minDistance(string word1, string word2)
        {
                // Let dp[i][j] denote the minimum number of operations required to convert the first i characters of word1 to the first j characters of word2.
                int i, j;
                int m = word1.length(), n = word2.length();
                vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
                for (i = 0; i <= m; i++) {
                        // Converting word1[0..=i] to an empty string requires i operations
                        dp[i][0] = i;
                }

                for (j = 0; j <= n; j++) {
                        // Converting an empty string to word2[0..=j] requires j operations
                        dp[0][j] = j;
                }

                for (i = 1; i <= m; i++) {
                        for (j = 1; j <= n; j++) {
                                if (word1[i - 1] == word2[j - 1]) {
                                        // No extra operation is needed
                                        dp[i][j] = dp[i - 1][j - 1];
                                } else {

                                        // dp[i-1][j] (delete word1[i-1])
                                        // dp[i][j-1] (insert word2[j-1])
                                        // dp[i-1][j-1] (replace word1[i-1] with word2[j-1])

                                        dp[i][j] = std::min({ dp[i][j - 1], dp[i - 1][j],
                                                              dp[i - 1][j - 1] }) +
                                                   1;
                                }
                        }
                }
                return dp[m][n];
        }
};

leetcode hot 100 rewrite

#include <string>
#include <vector>
#include <algorithm>

using std::string;
using std::vector;

class Solution {
    public:
        int minDistance(string word1, string word2)
        {
                int i, j, n1 = word1.size(), n2 = word2.size();
                // dp[i][j] represents the minimum number of steps to transform word1[0..i) into word2[0..j)
                vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1, 0));

                for (i = 0; i <= n1; i++)
                        dp[i][0] = i;

                for (j = 0; j <= n2; j++)
                        dp[0][j] = j;

                for (i = 1; i <= n1; i++) {
                        for (j = 1; j <= n2; j++) {
                                if (word1[i - 1] == word2[j - 1]) {
                                        dp[i][j] = dp[i - 1][j - 1];
                                } else {
                                        dp[i][j] = std::min({ dp[i][j - 1], dp[i - 1][j],
                                                              dp[i - 1][j - 1] }) +
                                                   1;
                                }
                        }
                }
                return dp[n1][n2];
        }
};