Recursive Java Solution (not most efficient, but help identify general DP problems)


  • 0
    S

    Basically, my solution is based on this set of lecture notes:
    http://www.cs.cmu.edu/~avrim/451f09/lectures/lect1001.pdf

    In terms of time and space efficiency, it's definitely not the best.
    But it helps us understand how to understand the general DP problems and also, the recursive logic is extremely simple to understand.

    If we extract the system stacks in which the recursive process happens, it's the iterative approach in which most people create a mxn matrix to store all the previous answers.

    Recursive - top down.
    Iterative - bottom up.

    public class EditDistance {
    
    int[][] array;
    int result = 0;
    
    public int minDistance(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        
        // store the previous results.
        array = new int[n1 + 1][n2 + 1];
    
        // Initialize the array such that we know if the value is -1, the result has not been 
        // computed.
        for (int i = 0; i < array.length; ++i) {
        	for (int j = 0; j < array[i].length; ++j)
        		array[i][j] = -1;
        }
        
        return editDistance(word1, n1, word2, n2);
        
    }
    
    
    public int editDistance(String word1, int m, String word2, int n) {
    	if (m == 0) return n;
    	if (n == 0) return m;
    	else {
    		
    		if (array[m][n] != -1) return array[m][n]; // If the result is already there, return.
    		
    		int min1 = Math.min(editDistance(word1, m - 1, word2, n) + 1, 
    				editDistance(word1, m, word2, n - 1) + 1);
    		
    		if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
    			result = Math.min(editDistance(word1, m - 1, word2, n - 1), min1);
    		}
    		else result = Math.min(editDistance(word1, m - 1, word2, n - 1) + 1, min1);
    	}
    	
    	array[m][n] = result; // Store the result in the array.
    	
    	return result;
    	
    }
    

    }


Log in to reply
 

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