583. Delete Operation for Two Strings

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minDistance(string word1, string word2) {
        
        //      e   a   t
        //  0   1   2   3
        //s 1   2   3   4
        //e 2   1   2   3
        //a 3   2   1   2

        int n = word1.size(), m = word2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1,0));
        for(int i=0;i<n+1;++i) dp[i][0] = i;
        for(int j=0;j<m+1;++j) dp[0][j] = j;
        for(int i=1;i<n+1;i++){
            for(int j = 1;j<m+1;j++){
                if(word1[i-1] !=word2[j-1]) dp[i][j] = min( dp[i-1][j],dp[i][j-1] ) +1; // insert or delete
                else dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp.back().back();
    }
};

analysis

  • time complexity O(nm)
  • space complexity O(nm)