dp c solution, the fastest solution


  • 0
    D
    int minDistance(char* word1, char* word2) {
    	int l1 = strlen(word1);
    	int l2 = strlen(word2);
        char **dp;
        dp = malloc(sizeof(char*) * (l1+1));
        for(int i = 0; i < l1+1; i++){
            dp[i] = malloc(l2+1);
        }
        for(int i = 0; i < l2+1; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i < l1+1; i++){
            dp[i][0] = i;
        }
    	for(int i = 1; i < l1+1; i++){
    	    for(int j = 1; j < l2+1; j++){
    	        if(word1[i-1] == word2[j-1]){
    	            dp[i][j] = dp[i-1][j-1];
    	        }else{
    	            int m = dp[i-1][j] > dp[i-1][j-1] ? dp[i-1][j-1] : dp[i-1][j];
    	            m = m > dp[i][j-1] ? dp[i][j-1] : m;
    	            dp[i][j] = m+1;
    	        }
    	    }
    	}
    	return dp[l1][l2];
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.