Dynamic Programming Solution in C++ with Algorithm Description
Algorithm Description  \n\n\n----------\n\n - Step 1:\n\nSet  n to be the length of word1;\nSet m to be the length of word2.  \nIf n = 0, return m and exit.  \n
**Algorithm Description**  \n\n\n----------\n\n - Step 1:\n\nSet  n to be the length of *word1*;\nSet m to be the length of *word2*.  \nIf n = 0, return m and exit.  \nIf m = 0, return n  and exit.  \nConstruct a matrix containing 0...n rows and 0...m columns.  \n  \n\n - Step 2:\n\nInitialize the first row       to 0...n.  \nInitialize the first column to 0...m.  \n  \n\n - Step 3:\n\nExamine each character of *word1* (i from 1 to  n).\n\n - Step 4:\n\nExamine each character of *word2*  (j from 1 to m).\n\n - Step 5:\n\nIf word1[i] == word2[j], the cost = 0.  \nIf word1[i] !=  word2[j], the cost = 1.  \n  \n\n - Step 6:\n\n   \nSet cell A [i, j] of the matrix equal to the minimum of:  \na) The cell immediately **above** plus 1:                               A[i - 1, j]    + 1.  \nb) The cell immediately **to the left** plus 1:                          A[i,  j - 1]    + 1.  \nc) The cell diagonally **above and to the left** plus the cost: A[i - 1, j - 1] + cost.  \n  \n\n - Step 7:\n\n   \nAfter the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell A[n, m]. \n\n\n----------\n\n\nHere is the code:\n\n    int minDistance(string word1, string word2) {\n        // Step 1\n        int n = word1.size(), m = word2.size();\n        if (n == 0)  return m;\n        if (m == 0)  return n;\n        int A[n + 1][m + 1];\n\n        // Step 2\n        for (int i = 0; i <= n; ++i)  A[i][0] = i;\n        for (int j = 0; j <= m; ++j)  A[0][j] = j;\n        \n        for (int i = 1; i <= n; ++i) {  // Step 3\n            char word1_i = word1[i-1];\n            for (int j = 1; j <= m; ++j) {  // Step 4\n                char word2_j = word2[j-1];\n                int cost = (word1_i == word2_j) ? 0 : 1;  // Step 5\n                A[i][j] = min(min(A[i-1][j]+1, A[i][j-1]+1), A[i-1][j-1]+cost);// Step 6\n            }\n        }\n        return A[n][m];  // Step 7\n    }
['C++']