Algorithm

LeetCode/Edit Distance

Problem Summary

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

(1) Insert a character
(2) Delete a character
(3) Replace a character

Solution

We can solve this problem with dynamic programming.
Suppose we are going to convert S[0…N] to T[0…M] and we take all operations from left to right, with the minimal number of steps being f[N][M].

If S[N] == T[M], f[N][M] = f[N-1][M-1]. Otherwise, we have three cases:

  1. Convert S[0…N] to T[0…M-1], then insert T[M] to the end of S. This will cost f[N][M-1] + 1.

  2. Convert S[0…N-1] to T[0…M], then delete S[N]. This will cost f[N-1][M] + 1.

  3. Convert S[0…N-1] to T[0…M-1], then replace S[N] with T[M]. This will cost f[N-1][M-1] + 1.

Code 1: O(N*M) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minDistance(string w1, string w2) {
        int n = w1.length(), m = w2.length();
        if (n == 0)
            return m;
        if (m == 0)
            return n;
        
        vector<vector<int>> f(n+1, vector<int>(m+1));
        for (int j = 1; j <= m; ++j)
            f[0][j] = j;
        
        for (int i = 1; i <= n; ++i) {
            f[i][0] = i;
            for (int j = 1; j <= m; ++j) {
                if (w1[i-1] == w2[j-1])
                    f[i][j] = f[i-1][j-1];
                else
                    f[i][j] = min(f[i-1][j-1], min(f[i-1][j], f[i][j-1])) + 1;
            }
        }
        
        return f[n][m];
    }
};

Code 2: O(M) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minDistance(string w1, string w2) {
        int n = w1.length(), m = w2.length();
        if (n == 0)
            return m;
        if (m == 0)
            return n;
        
        vector<int> f(m+1);
        for (int j = 1; j <= m; ++j)
            f[j] = j;
        
        for (int i = 1; i <= n; ++i) {
            int pre = f[0]; // pre : f[i-1][j-1]
            f[0] = i;
            for (int j = 1; j <= m; ++j) {
                int tmp = f[j];
                f[j] = min(min(f[j], f[j-1]) + 1, pre + (w1[i-1] == w2[j-1] ? 0 : 1));
                pre = tmp;
            }
        }
        
        return f[m];
    }
};