Java 9 ms. That moment when you suck at DP and write a solution that beats 99.16%


  • 0
    A

    I suck at DP. Whenever I come up with a DP solution it's either ugly, complicated, has a ton of unnecessary variables or all of the above. This solution is no different: it's recursive, it's ugly, it's unnecessarily long. But, because of all the if statements and early returns that terminate the recursion as early as needed, this solution runs in 9ms and beats 99.16% of submissions. Go figure.

    My next step will be to actually write a pretty solution even if it's slower.

    public int minDistance(String word1, String word2) {
        int[][] mem = new int[word1.length()+1][word2.length()+1];
        for(int[] row : mem) Arrays.fill(row,-1);
        mem[word1.length()][word2.length()] = 0;
        return minDist(word1,0,word2,0,mem);
    }
    
    public int minDist(String word1, int i, String word2, int j, int[][] mem) {
        if (i == word1.length() && j == word2.length()) return 0;
        if (i == word1.length()) {
            mem[i][j] = mem[i][j+1] != -1 ? mem[i][j+1] + 1 : minDist(word1,i,word2,j+1,mem) + 1;
            return mem[i][j];
        }
        if (j == word2.length()) {
            mem[i][j] = mem[i+1][j] != -1 ? mem[i+1][j] + 1 : minDist(word1,i+1,word2,j,mem) + 1;
            return mem[i][j];
        }
        if (word1.charAt(i) == word2.charAt(j)) {
            mem[i][j] = mem[i+1][j+1] != -1 ? mem[i+1][j+1] : minDist(word1,i+1,word2,j+1,mem);
            return mem[i][j];
        }
        int w1 = mem[i+1][j] != -1 ? mem[i+1][j] + 1 : minDist(word1,i+1,word2,j,mem) + 1;
        int w2 = mem[i][j+1] != -1 ? mem[i][j+1] + 1 : minDist(word1,i,word2,j+1,mem) + 1;
        int w1w2 = mem[i+1][j+1] != -1 ? mem[i+1][j+1] + 1: minDist(word1,i+1,word2,j+1,mem) + 1;
        mem[i][j] = Math.min(w1w2, Math.min(w1,w2));
        return mem[i][j];
    }

Log in to reply
 

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