Java DP solution with optimized O(N) space


  • 1
    C

    This solution use O(N2) Space, but it more readable:

    public class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            int[][] map = new int[len1+1][len2+1];
            
            for (int i=0; i<=len1; i++) {
                map[i][0] = i;
            }
            
            for (int j=0; j<=len2; j++) {
                map[0][j] = j;
            }
            
            for (int i=0; i<len1; i++) {
                for (int j=0; j<len2; j++) {
                    if (word1.charAt(i) == word2.charAt(j)) {
                        map[i+1][j+1] = map[i][j];
                    } else {
                        map[i+1][j+1] = Math.min(map[i][j+1], map[i+1][j]) + 1;
                    }
                }
            }
            
            return map[len1][len2];
        }
    }
    

    This next solution is based on the above, but is optimized to use one O(N) space:

    public class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length();
            int len2 = word2.length();
            int[] map = new int[len2+1];
            
            for (int j=0; j<=len2; j++) {
                map[j] = j;
            }
            
            for (int i=0; i<len1; i++) {
                int[] newmap = new int[len2+1];
                newmap[0] = i + 1;
                for (int j=0; j<len2; j++) {
                    if (word1.charAt(i) == word2.charAt(j)) {
                        newmap[j+1] = map[j];
                    } else {
                        newmap[j+1] = Math.min(map[j+1], newmap[j]) + 1;
                    }
                }
                map = newmap;
            }
            
            return map[len2];
        }
    }
    

Log in to reply
 

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