Dynamic Programming and Memoization Solution


  • 0
    L

    DP:

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            if (word1.empty() || word2.empty()) return max(word1.size(), word2.size());
            vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 1 << 30));
            for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
            for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;
            for (int i = 1; i <= word1.size(); i++)
                for (int j = 1; j <= word2.size(); j++)
                    if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            return dp[word1.size()][word2.size()];
        }
    };
    

    Memoization

    class Solution {
        unordered_map<string, int> mem;
        int match(const string &word1, const string &word2, int idx1, int idx2) {
            auto id = to_string(idx1) + " " + to_string(idx2);
            if (mem.count(id)) {
                return mem[id];
            } else if (idx2 == word2.size() || idx1 == word1.size()) {
                return word1.size() - idx1 + word2.size() - idx2;
            }
            int subans = INT_MAX;
            auto pos = word1.find(word2[idx2], idx1);
            if (pos != string::npos) subans = pos - idx1 + match(word1, word2, pos + 1, idx2 + 1);
            subans = min(subans, 1 + match(word1, word2, idx1, idx2 + 1));
            return mem[id] = subans;
        }
    public:
        int minDistance(string word1, string word2) {
             return match(word1, word2, 0, 0);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.