Edit Distance

class Solution {
public:
    map, int> m;
    int minDistance(string word1, string word2) {
        return minDistHelper(word1, word2, 0, 0);
    }
   
    int minDistHelper(string const& word1, string const& word2, int const index1, int const index2) {
        pair p = make_pair(index1, index2);
        if (m[p]) return m[p];
        if (index1 == word1.size()) return word2.size() - index2;
        if (index2 == word2.size()) return word1.size() - index1;
       
        if (word1[index1] == word2[index2]) return minDistHelper(word1, word2, index1 + 1, index2 + 1);
        m[p] = 1 + min(minDistHelper(word1, word2, index1+1, index2+1), min(minDistHelper(word1, word2, index1+1, index2), minDistHelper(word1, word2, index1, index2+1)));
        return m[p];
    }
};