# Java DP solution with optimized O(N) space

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

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