72. Edit Distance

,

Dynamic Programming

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int helper(vector< vector<int> >&dp, string word1, string word2, int i, int j){
        if(dp[i][j] != -1)
            return dp[i][j];
        
        if(word1[i] == word2[j])
            return dp[i][j] = helper(dp,word1, word2, i+1, j+1);

        return dp[i][j] = min({helper(dp,word1, word2, i+1, j+1), helper(dp,word1, word2, i+1, j), helper(dp,word1, word2, i, j+1)}) + 1;
    }
    int minDistance(string word1, string word2) {
        vector< vector<int> >dp(word1.size() + 1, vector<int>(word2.size() + 1, -1));
        for(int i = 0; i <= word1.size(); i++){
            dp[i][word2.size()] = word1.size() - i;
        }
        for(int j = 0; j <= word2.size(); j++){
            dp[word1.size()][j] = word2.size() - j;
        }
        return helper(dp, word1, word2, 0, 0);
    }
};

Tabulation

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 word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector< vector<int> >dist(m+1, vector<int>(n+1));
        dist[0][0] = 0;
        for(int i = 1; i <= m; i++){
            dist[i][0] = i;
        }
        for(int j = 1; j <= n; j++){
            dist[0][j] = j;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1[i-1] == word2[j-1]){
                    dist[i][j] = dist[i-1][j-1];
                }
                else{
                    dist[i][j] = min({dist[i-1][j], dist[i][j-1], dist[i-1][j-1]}) + 1;
                }
            }
        }
        return dist[m][n];
    }
};

Optimized to two 1D arrays

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 word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int>>dist(2, vector<int>(n+1));
        int prev = 0, cur = 1;
        for(int j = 0; j <= n; j++){
            dist[prev][j] = j;//dist[0][j] = j
        }
        for(int i = 1; i <= m; i++){
            dist[cur][0] = i;//dist[i][0] = i
            for(int j = 1; j <= n; j++){
                if(word1[i-1] == word2[j-1]){
                    dist[cur][j] = dist[prev][j-1];
                }
                else{
                    dist[cur][j] = min({dist[prev][j], dist[cur][j-1], dist[prev][j-1]}) + 1;
                }
            }
            cur ^= 1;
            prev ^= 1;
        }
        return dist[prev][n];
    }
};

Optimized to one 1D array

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 word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<int>dist(n+1);
        for(int j = 0; j <= n; j++){
            dist[j] = j;//dist[0][j] = j
        }
        for(int i = 1; i <= m; i++){
            int prev_j_1 = dist[0];// i-1
            dist[0] = i;//dist[i][0] = i
            for(int j = 1; j <= n; j++){
                int prev_j = dist[j];// dist[i-1][j]
                if(word1[i-1] == word2[j-1]){
                    dist[j] = prev_j_1;// dist[i-1][j-1]
                }
                else{
                    dist[j] = min({prev_j, dist[j-1], prev_j_1}) + 1;// dist[i-1][j], dist[i][j-1], dist[i-1][j-1]
                }
                prev_j_1 = prev_j;
            }
        }
        return dist[n];
    }
};

Brute Force

get MLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int helper(string word1, string word2, int i, int j){
        if(i == word1.length())
            return word2.length() - j;
        if(j == word2.length())
            return word1.length() - i;
        
        if(word1[i] == word2[j])
            return helper(word1, word2, i+1, j+1);// no operation needed

        return min({helper(word1, word2, i+1, j+1), helper(word1, word2, i+1, j), helper(word1, word2, i, j+1)}) + 1;// replace, delete, insert
    }
    int minDistance(string word1, string word2) {
        return helper(word1, word2, 0, 0);
    }
};