Clean Solution in 11 Lines


  • 1
        int[] prev = new int[word2.length()+1]; int[] curr = new int[word2.length()+1];
    	for(int j = 0; j<prev.length; j++) prev[j] = curr[j] = j;
    	for(int i=0;i<word1.length();i++) {
    		curr[0] = i+1;
    		for(int j=1;j<curr.length;j++) {
    			int sub = (word1.charAt(i)==word2.charAt(j-1))?0:1;
    			curr[j] = Math.min(prev[j-1]+sub, Math.min(curr[j-1]+1, prev[j]+1));
    		}
    		prev=Arrays.copyOf(curr,curr.length);
    	}
    	return curr[curr.length-1];
    

    I'm using the Levenshtein Distance algorithm, the version using just two lines of the matrix of distances. As we need just the previous line to compute the current line, there is no need to store the entire matrix.

    Best running time in Java 328ms.


Log in to reply
 

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