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 class Solution {
02 public:
03     int minDistance(string word1, string word2) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=word1.size();
07         int m=word2.size();
08         if(n==0)
09             return m;
10         if(m==0)
11             return n;
12         vector<int*> A(n+1);
13         for(int i=0;i<=n;i++)
14         {
15             A[i]=new int[m+1];
16             for(int j=0;j<=m;j++)
17             {
18                 A[i][j]=0;
19             }
20         }
21         int p=n;
22         int q=m;
23         A[p][q]=0;
24         for(int i=p1;i>=0;i)
25         {
26             A[i][q]=A[i+1][q]+1;
27         }
28         for(int i=q1;i>=0;i)
29         {
30             A[p][i]=A[p][i+1]+1;
31         }
32         while((p>0)&&(q>0))
33         {
34             p;
35             q;
36             if(word1[p]==word2[q])
37             {
38                 A[p][q]=A[p+1][q+1];
39             }
40             else
41             {
42                  A[p][q]=A[p+1][q]<A[p][q+1]?
43                    A[p+1][q]+1:A[p][q+1]+1;
44                  A[p][q]=A[p][q]<A[p+1][q+1]+1?
45                    A[p][q]:A[p+1][q+1]+1;
46             }
47             for(int i=p1;i>=0;i)
48             {
49                 if(word1[i]==word2[q])
50                 {
51                     A[i][q]=A[i+1][q+1];
52                 }
53                 else
54                 {
55                     A[i][q]=A[i+1][q]<A[i][q+1]?
56                       A[i+1][q]+1:A[i][q+1]+1;
57                     A[i][q]=A[i][q]<A[i+1][q+1]+1?
58                       A[i][q]:A[i+1][q+1]+1;
59                 }
60             }
61             for(int i=q1;i>=0;i)
62             {
63                 if(word1[p]==word2[i])
64                 {
65                     A[p][i]=A[p+1][i+1];
66                 }
67                 else
68                 {
69                     A[p][i]=A[p+1][i]<A[p][i+1]?
70                       A[p+1][i]+1:A[p][i+1]+1;
71                     A[p][i]=A[p][i]<A[p+1][i+1]+1?
72                       A[p][i]:A[p+1][i+1]+1;
73                 }
74             }
75         }
76         return A[0][0];
77     }
78 };
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