# Java Solution with Time Complexity O(m*n) and Space Complexity O(2n)

• We can solve the problem with Time Complexity O(m*n) and Space Complexity O(2n). Look at minDistance3 method.
We do not need to store all the rows. We just need to store the data of previous row. So maximum 2 rows of data at any point of time.

``````class Solution {
public int minDistance(String word1, String word2) {

//  Time O(3^m), where m is the len of str1
//  return minDistance(word1.toCharArray(), word2.toCharArray(), word1.length()-1, word2.length()-1);
//  Time O(m*n) Space O(m*n)
//  return minDistance2(word1.toCharArray(), word2.toCharArray());
// Time O(m*n) Space O(m);
return minDistance3(word1.toCharArray(), word2.toCharArray());

}

public int minDistance(char []w1,char []w2,  int i, int j){
int count = 0;

if( i == -1 && j == -1){
return 0;
}

if( i == -1 ){
return j+1;
}

if( j == -1 ){
return i+1;
}

if(w1[i] == w2[j]){
count = minDistance(w1,w2,i-1,j-1);
}else{
int insertCount = 1 + minDistance(w1,w2,i,j-1);
int delCount = 1 + minDistance(w1,w2,i-1,j);
int repCount = 1 + minDistance(w1,w2,i-1,j-1);
count = Math.min(insertCount,Math.min(delCount, repCount));
}

return count;
}

public int minDistance2(char []w1, char []w2){
int i = w1.length;
int j = w2.length;

if( i == 0 && j == 0){
return 0;
}

if( i == 0 ){
return j;
}

if( j == 0 ){
return i;
}

int [][]minDis = new int[i+1][j+1];

for(int w1Indx = 0 ; w1Indx < i+1 ; w1Indx++){

for(int w2Indx = 0; w2Indx < j+1; w2Indx++){
if(w1Indx == 0){
minDis[w1Indx][w2Indx] = w2Indx;
continue;
}
if(w2Indx == 0){
minDis[w1Indx][w2Indx] = w1Indx;
continue;
}
if(w1[w1Indx-1] == w2[w2Indx-1]){
minDis[w1Indx][w2Indx] =  minDis[w1Indx-1][w2Indx-1];
}else{
minDis[w1Indx][w2Indx] = 1 + Math.min( minDis[w1Indx-1][w2Indx], Math.min(minDis[w1Indx][w2Indx-1], minDis[w1Indx-1][w2Indx-1]));
}
}
}
return minDis[i][j];
}

public int minDistance3(char []w1, char []w2){
int m = w1.length;
int n = w2.length;

if( m == 0 && n == 0){
return 0;
}

if( m == 0 ){
return n;
}

if( n == 0 ){
return m;
}

int [][]minDis = new int[2][n+1];

int dp = 0;

for(int w1Indx = 0 ; w1Indx < m+1 ; w1Indx++){
dp = w1Indx & 1;
for(int w2Indx = 0; w2Indx < n+1; w2Indx++){
if(w1Indx == 0){
minDis[dp][w2Indx] = w2Indx;
continue;
}
if(w2Indx == 0){
minDis[dp][w2Indx] = w1Indx;
continue;
}
if(w1[w1Indx-1] == w2[w2Indx-1]){
minDis[dp][w2Indx] =  minDis[1-dp][w2Indx-1];
}else{
minDis[dp][w2Indx] = 1 + Math.min( minDis[1-dp][w2Indx], Math.min(minDis[dp][w2Indx-1], minDis[1-dp][w2Indx-1]));
}
}
}
return minDis[dp][n];
}
}
``````

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