Leetcode-Problems-Solutions/Edit Distance at main · AgrawalJitendra12/Leetcode-Problems-Solutions · GitHub

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
27
class Solution {
public:
    int minDistance(string word1, string word2) {
         int m = word1.length(), n = word2.length();
        vector<vector<int>> memo(m+1, vector<int>(n+1, -1));
        return editDistance(word1, word2, m, n, memo);
    }

    int editDistance(string& word1, string& word2, int m, int n, vector<vector<int>>& memo){
        if(m == 0) return memo[m][n] = n;
        if(n == 0) return memo[m][n] = m;

        if(memo[m][n] != -1)
            return memo[m][n];

        if(word1[m-1] == word2[n-1])
            return memo[m][n] = editDistance(word1, word2, m-1, n-1, memo);
        else{
            int insertChar = editDistance(word1, word2, m, n-1, memo);
            int deleteChar = editDistance(word1, word2, m-1, n, memo);
            int replaceChar = editDistance(word1, word2, m-1, n-1, memo);

            return memo[m][n] = 1 + min({insertChar, deleteChar, replaceChar});
        }

    }
};