// Other Approaches

Space Complex Solution: In the above-given method we require O(m x n) space. This will not be suitable if the length of strings is greater than 2000 as it can only create 2D arrays.array of 2000 x 2000. To fill a row in DP arrays.array we require only one row the upper row. For example, if we are filling the i = 10 rows in DP arrays.array we require only values of 9th row. So we simply create a DP arrays.array of 2 x str1 length. This approach reduces the space complexity. Here is the C++ implementation of the above-mentioned problem

// A Space efficient Dynamic Programming

// based Java program to find minimum

// number operations to convert str1 to str2

import java.util.*;

class GFG

{

static void EditDistDP(String str1, String str2)

{

int len1 = str1.length();

int len2 = str2.length();

// Create a DP arrays.array to memoize result

// of previous computations

int [][]DP = new int[2][len1 + 1];

// Base condition when second String

// is empty then we remove all characters

for (int i = 0; i <= len1; i++)

DP[0][i] = i;

// Start filling the DP

// This loop run for every

// character in second String

for (int i = 1; i <= len2; i++)

{

// This loop compares the char from

// second String with first String

// characters

for (int j = 0; j <= len1; j++)

{

// if first String is empty then

// we have to perform add character

// operation to get second String

if (j == 0)

DP[i % 2][j] = i;

// if character from both String

// is same then we do not perform any

// operation . here i % 2 is for bound

// the row number.

else if (str1.charAt(j - 1) == str2.charAt(i - 1)) {

DP[i % 2][j] = DP[(i - 1) % 2][j - 1];

}

// if character from both String is

// not same then we take the minimum

// from three specified operation

else {

DP[i % 2][j] = 1 + Math.min(DP[(i - 1) % 2][j],

Math.min(DP[i % 2][j - 1],

DP[(i - 1) % 2][j - 1]));

}

}

}

// after complete fill the DP arrays.array

// if the len2 is even then we end

// up in the 0th row else we end up

// in the 1th row so we take len2 % 2

// to get row

System.out.print(DP[len2 % 2][len1] +"\n");

}

// Driver program

public static void main(String[] args)

{

String str1 = "food";

String str2 = "money";

EditDistDP(str1, str2);

}

}

// This code is contributed by aashish1995

Output

4

Time Complexity: O(m x n)

Auxiliary Space: O( m )

This is a memoized version of recursion i.e. Top-Down DP:

import java.util.*;

class GFG

{

static int minDis(String s1, String s2,

int n, int m, int[][]dp)

{

// If any String is empty,

// return the remaining characters of other String

if(n == 0)

return m;

if(m == 0)

return n;

// To check if the recursive tree

// for given n & m has already been executed

if(dp[n][m] != -1)

return dp[n][m];

// If characters are equal, execute

// recursive function for n-1, m-1

if(s1.charAt(n - 1) == s2.charAt(m - 1))

{

if(dp[n - 1][m - 1] == -1)

{

return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);

}

else

return dp[n][m] = dp[n - 1][m - 1];

}

// If characters are nt equal, we need to

// find the minimum cost out of all 3 operations.

else

{

int m1, m2, m3; // temp variables

if(dp[n-1][m] != -1)

{

m1 = dp[n - 1][m];

}

else

{

m1 = minDis(s1, s2, n - 1, m, dp);

}

if(dp[n][m - 1] != -1)

{

m2 = dp[n][m - 1];

}

else

{

m2 = minDis(s1, s2, n, m - 1, dp);

}

if(dp[n - 1][m - 1] != -1)

{

m3 = dp[n - 1][m - 1];

}

else

{

m3 = minDis(s1, s2, n - 1, m - 1, dp);

}

return dp[n][m] = 1 + Math.min(m1, Math.min(m2, m3));

}

}

// Driver program

public static void main(String[] args)

{

String str1 = "voldemort";

String str2 = "dumbledore";

int n= str1.length(), m = str2.length();

int[][] dp = new int[n + 1][m + 1];

for(int i = 0; i < n + 1; i++)

Arrays.fill(dp[i], -1);

System.out.print(minDis(str1, str2, n, m, dp));

}

}

Output

7