Saturday, May 11, 2013

Leetcode: Edit Distance in C++



Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Solution:

int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > inner(m+1,vector<int>(n+1, 0));
        for(int i=0;i<=m;i++)
        {
            inner[i][0] = i;//word2 is empty
        }
        for(int i=0;i<=n;i++)
        {
            inner[0][i] = i; //word1 is empty
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(word1[i-1] == word2[j-1])
                {
                    inner[i][j] = inner[i-1][j-1];
                }
                else
                {
                    int ins = inner[i][j-1]+1; //insert
                    int del = inner[i-1][j]+1;  //delete
                    int rep = inner[i-1][j-1]+1; //replace
                    inner[i][j] = min(ins, min(del, rep));
                }
            }
        }
        return inner[m][n];
    }

No comments:

Post a Comment