JS(LCS) 168ms


  • 0
    C

    wiki

    At first time, i used dict instead of array, but it's too slow, following is AC code.

    var minDistance = function(word1, word2) {
    	var c = [],
    		m = word1.length, n = word2.length;
    	
    	for(var i = 0; i<= m; ++i){
    		c[i] = new Array(m);
    		c[i][0] = 0;
    	}
    
    	for(var j = 0; j<=n; ++j){
    		c[0][j] = 0;
    	}
    
    	for(var i = 1; i <= m; ++i){
    		for(var j = 1; j <= n; ++j){
    			// console.log(i, j, word1[i-1], word2[j-1]);
    			if(word1[i-1] === word2[j-1]){
    				c[i][j] = c[i-1][j-1] + 1;
    			} else {
    				c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
    			}
    		}
    	}
    	// console.log(c);
    	return m + n - 2 * c[m][n];
    };
    

Log in to reply
 

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