583. deleting two strings - Dynamic Planning

583. Deletion of two strings

Give two words word1 and word2 , Return makes word1 and word2 The same minimum number of steps required .

Every step You can delete a character from any string .

Example 1：

Input : word1 = “sea”, word2 = “eat”
Output : 2
explain : The first step will be “sea” Turn into “ea” , The second step will be "eat " Turn into “ea”

Example 2:

Input ：word1 = “leetcode”, word2 = “etco”
Output ：4

This problem can be transformed into solving the longest common subsequence , Using dynamic programming algorithms , More appropriate ：

int minDistance(char * word1, char * word2){
    
    int n=strlen(word1),m=strlen(word2);
    int dp[n+1][m+1];
    int i,j;
    for(i=0;i<=m;i++){
    
        dp[0][i]=0;
    }
     for(i=0;i<=n;i++){
    
        dp[i][0]=0;
    }

    for(i=1;i<=n;i++){
    
        char ch1=word1[i-1];
        for(j=1;j<=m;j++){
    
            char ch2=word2[j-1];
            if(ch2==ch1){
    
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
    
               
                if(dp[i-1][j]>dp[i][j-1]){
    
                     dp[i][j]=dp[i-1][j];

                }
                else{
    
                     dp[i][j]=dp[i][j-1];

                }
               
            }
           // printf("%d index %d %d ",dp[i][j],i,j);
            
        }
    }

    return n-dp[n][m]+m-dp[n][m];
    

}