Optimizing Space Complexity
The dynamic programming approach discussed earlier for calculating edit distance uses a 2D matrix dp of dimensions (m + 1) x (n + 1), where m and n are the lengths of the input strings. This results in a space complexity of O(m x n). However, we can optimize the space complexity of the algorithm by using a 1D array to store only the previous row of the matrix.
Let's take a look at an optimized version of the code:
TEXT/X-CSHARP
1using System;
2
3namespace EditDistance {
4 public class EditDistanceAlgorithm {
5 public static int CalculateEditDistance(string str1, string str2) {
6 int[] dp = new int[str2.Length + 1];
7
8 for (int j = 0; j <= str2.Length; j++) { // Initialize the first row
9 dp[j] = j;
10 }
11
12 for (int i = 1; i <= str1.Length; i++) {
13 int prev = dp[0];
14 dp[0] = i;
15
16 for (int j = 1; j <= str2.Length; j++) {
17 int temp = dp[j];
18
19 if (str1[i - 1] == str2[j - 1]) {
20 dp[j] = prev;
21 }
22 else {
23 dp[j] = Math.Min(prev + 1, Math.Min(dp[j - 1] + 1, dp[j] + 1));
24 }
25
26 prev = temp;
27 }
28 }
29
30 return dp[str2.Length];
31 }
32
33 public static void Main(string[] args) {
34 string str1 = "algorithm";
35 string str2 = "logarithm";
36
37 int distance = CalculateEditDistance(str1, str2);
38 Console.WriteLine("Edit distance between " + str1 + " and " + str2 + " is " + distance);
39 }
40 }
41}xxxxxxxxxx38
}using System;namespace EditDistance { public class EditDistanceAlgorithm { public static int CalculateEditDistance(string str1, string str2) { int[,] dp = new int[str1.Length + 1, str2.Length + 1]; for (int i = 0; i <= str1.Length; i++) { dp[i, 0] = i; } for (int j = 0; j <= str2.Length; j++) { dp[0, j] = j; } for (int i = 1; i <= str1.Length; i++) { for (int j = 1; j <= str2.Length; j++) { if (str1[i - 1] == str2[j - 1]) { dp[i, j] = dp[i - 1, j - 1]; } else { dp[i, j] = Math.Min(dp[i - 1, j - 1] + 1, Math.Min(dp[i, j - 1] + 1, dp[i - 1, j] + 1)); } } } return dp[str1.Length, str2.Length]; }OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
