LC72 Edit Distance

 1 class Solution {
 2 public:
 3     int minDistance(string word1, string word2) {
 4         if(word1.size()==0||word2.size()==0)
 5             return word1.size()==0?word2.size():word1.size();
 6         int width=word1.size()+1;
 7         int height=word2.size()+1;
 8         vector<vector<int> > iv(height,vector<int>(width,0));
 9         for(int i=0;i<width;i++)
10             iv[0][i]=i;
11         for(int i=0;i<height;i++)
12             iv[i][0]=i;
13         for(int i=1;i<height;i++)
14         {
15             for(int j=1;j<width;j++)
16             {
17                 if(word1[j-1]==word2[i-1])
18                 {
19                     iv[i][j]=iv[i-1][j-1];
20                 }
21                 else
22                 {
23                     int tmp=(iv[i-1][j]>iv[i][j-1])?(iv[i][j-1]+1):(iv[i-1][j]+1);
24                     iv[i][j]=(tmp>(iv[i-1][j-1]+1))?(iv[i-1][j-1]+1):tmp;
25                 }
26             }
27         }
28         return iv[word2.size()][word1.size()];
29     }
30 };