Dynamic Programming Solution in C++ with Algorithm Description


  • 12
    N

    Algorithm Description


    • Step 1:

    Set n to be the length of word1;
    Set m to be the length of word2.
    If n = 0, return m and exit.
    If m = 0, return n and exit.
    Construct a matrix containing 0...n rows and 0...m columns.

    • Step 2:

    Initialize the first row to 0...n.
    Initialize the first column to 0...m.

    • Step 3:

    Examine each character of word1 (i from 1 to n).

    • Step 4:

    Examine each character of word2 (j from 1 to m).

    • Step 5:

    If word1[i] == word2[j], the cost = 0.
    If word1[i] != word2[j], the cost = 1.

    • Step 6:

    Set cell A [i, j] of the matrix equal to the minimum of:
    a) The cell immediately above plus 1: A[i - 1, j] + 1.
    b) The cell immediately to the left plus 1: A[i, j - 1] + 1.
    c) The cell diagonally above and to the left plus the cost: A[i - 1, j - 1] + cost.

    • Step 7:

    After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell A[n, m].


    Here is the code:

    int minDistance(string word1, string word2) {
        // Step 1
        int n = word1.size(), m = word2.size();
        if (n == 0)  return m;
        if (m == 0)  return n;
        int A[n + 1][m + 1];
    
        // Step 2
        for (int i = 0; i <= n; ++i)  A[i][0] = i;
        for (int j = 0; j <= m; ++j)  A[0][j] = j;
        
        for (int i = 1; i <= n; ++i) {  // Step 3
            char word1_i = word1[i-1];
            for (int j = 1; j <= m; ++j) {  // Step 4
                char word2_j = word2[j-1];
                int cost = (word1_i == word2_j) ? 0 : 1;  // Step 5
                A[i][j] = min(min(A[i-1][j]+1, A[i][j-1]+1), A[i-1][j-1]+cost);// Step 6
            }
        }
        return A[n][m];  // Step 7
    }

  • 0
    G

    nice code. 6(a) is inserting, 6(b) is deleting, 6(c) is replacing.


  • 0
    S

    6(a) is deleting, cause delete element index i in word1, 6(b) is inserting last element j in word2 to word1


  • 0
    H

    It's not that complicated as I thought


  • 0
    X

    http://web.stanford.edu/class/cs124/lec/med.pdf
    This is a famous algorithm.
    Do we have to fully understand how it works and why it's like that?


Log in to reply
 

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