【leetcode】Edit Distance

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 characterb) Delete a characterc) 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<vector<int> > dp(n1+1,vector<int>(n2+1));

13        

14         int **dp=new int*[n1+1];

15         for(int i=0;i<n1+1;i++)

16         {

17             dp[i]=new int[n2+1];

18         }

19        

20        

21         dp[0][0]=0;

22         for(int i=1;i<=n1;i++)

23         {

24             dp[i][0]=i;

25         }

26         for(int j=1;j<=n2;j++)

27         {

28             dp[0][j]=j;

29         }

30        

31         for(int i=1;i<=n1;i++)

32         {

33             for(int j=1;j<=n2;j++)

34             {

35                

36                 if(word1[i-1]==word2[j-1])

37                 {

38                     dp[i][j]=dp[i-1][j-1];

39                 }

40                 else

41                 {

42                     dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;

43                 }

44             }

45         }

46        

47         int result=dp[n1][n2];

48         for(int i=0;i<n1+1;i++)

49         {

50             delete[] dp[i];

51         }

52        

53         return result;

54     }

55 };