Exactly the same as edit distance.


  • 0
    H
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m = word1.size();
            int n = word2.size();
            if (!m)
                return n;
            else if (!n)
                return m;
            else {
                vector<vector<int>> table(m+1, vector<int>(n+1, 0));
                for (int i = 0; i <= m; i++)
                    table[i][0] = i;
                for (int i = 0; i <= n; i++)
                    table[0][i] = i;            
                
                for (int row = 1; row <= m; row++){
                    for (int col = 1; col <= n; col++) {
                        if (word1[row-1] == word2[col-1])
                            table[row][col] = table[row-1][col-1];
                        else
                            table[row][col] = min(table[row][col-1] + 1, table[row-1][col] + 1); // disable replace operation in edit distance problem
                    }
                }
                return table[m][n];
            }
        }
    };
    

Log in to reply
 

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