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

 

采用动态规划求解

1. d[0, j] = j;

2. d[i, 0] = i;

3. d[i, j] = d[i-1, j - 1] if A[i] == B[j]

4. d[i, j] = min(d[i-1, j - 1], d[i, j - 1], d[i-1, j]) + 1  if A[i] != B[j]

 

1 class Solution { 2 public: 3     int minDistance(string word1, string word2) { 4         5         int n1=word1.length(); 6         int n2=word2.length(); 7         8         if(n1==0) return n2; 9         if(n2==0) return n1;10  11         //采用二维数组效率更高 12         //vector
      
       
         > dp(n1+1,vector
        
         (n2+1));13        14         int **dp=new int*[n1+1];15         for(int i=0;i