Edit Distance

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

C++:
01 int minDistance(string word1, string word2) {
02        int n=word1.size();
03        int m=word2.size();
04        int A[n+1][m+1];
05        for(int i=0;i<=n;i++)
06         for(int j=0;j<=m;j++)
07             A[i][j]=0;
08        for(int i=0;i<=m;i++)
09             A[n][i]=mi;
10        for(int i=0;i<=n;i++)
11             A[i][m]=ni;
12        for(int i=n1;i>=0;i){
13            for(int j=m1;j>=0;j){
14                int a=A[i+1][j];
15                int b=A[i][j+1];
16                int c=A[i+1][j+1];
17                if(word1[i]==word2[j])
18                   c;
19                a=a<b?a:b;
20                a=a<c?a:c;
21                A[i][j]=1+a;
22            }
23        }
24        return A[0][0];
25 }
Advertisements
This entry was posted in Dynamic programming, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s