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

• 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];
}``````

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