C++ 6 lines DP O(n * m) and 4 lines DFS + Memo


  • 1
    V

    1. DP
    The transition function is the minimum of three cases:

    • Skip character in both string (dp[i - 1][j - 1]).
      • Add two deleted characters if the character is different
      • Add zero deleted characters if the character is the same (w1[i] == w2[j])
    • Skip character in the first string (dp[i - 1][j]). Add one deleted character
    • Skip character in the second string (dp[i][j - 1]). Add one deleted one character
    int minDistance(string w1, string w2) {
        if (w1.size() == 0 || w2.size() == 0) return w1.size() + w2.size();
        vector<vector<int>> dp(w1.size(), vector<int>(w2.size(), 0));
        for (int i = 0; i < w1.size(); ++i)
            for (int j = 0; j < w2.size(); ++j)
                dp[i][j] = min((i == 0 || j == 0 ? max(i, j) : dp[i - 1][j - 1]) + (w1[i] == w2[j] ? 0 : 2),
                    1 + min(i == 0 ? j + 1 : dp[i - 1][j], j == 0 ? i + 1 : dp[i][j - 1]));
        return dp[w1.size() - 1][w2.size() - 1];
    }
    

    2. BSF + Memo

    int minDistance(string& w1, string& w2, int p1, int p2, vector<vector<int>>& dp) {
        if (p1 == w1.size() || p2 == w2.size()) return w1.size() - p1 + w2.size() - p2;
        return dp[p1][p2] != - 1 ? dp[p1][p2] : dp[p1][p2] = 
            min(w1[p1] == w2[p2] ? minDistance(w1, w2, p1 + 1, p2 + 1, dp) : INT_MAX,
                1 + min(minDistance(w1, w2, p1 + 1, p2, dp), minDistance(w1, w2, p1, p2 + 1, dp)));
    }
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), -1));
        return minDistance(word1, word2, 0, 0, dp);
    }
    

Log in to reply
 

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