Sponsored
Sponsored
This approach uses a 2D array to store the edit distances between all prefixes of both strings. By building solutions for smaller subproblems, we can efficiently calculate the solution for the entire problem.
We define dp[i][j] as the edit distance between the first i characters of word1 and the first j characters of word2. The recursion is based on comparing the last characters of the current substrings. If they are the same, the edit distance is the same as dp[i-1][j-1], otherwise, we add 1 (to account for an edit operation) and consider the minimum edit distance found after each possible operation: insertion, deletion, or replacement.
Time Complexity: O(m * n) where m and n are the lengths of word1 and word2 respectively, as we compute values for each combination of indices.
Space Complexity: O(m * n) for storing the dp table.
1#include <string.h>
2#include <stdio.h>
3
4int minDistance(char* word1, char* word2) {
5 int m = strlen(word1);
6 int n = strlen(word2);
7 int dp[m + 1][n + 1];
8
9 for (int i = 0; i <= m; i++) {
10 dp[i][0] = i;
11 }
12 for (int j = 0; j <= n; j++) {
13 dp[0][j] = j;
14 }
15
16 for (int i = 1; i <= m; i++) {
17 for (int j = 1; j <= n; j++) {
18 if (word1[i - 1] == word2[j - 1]) {
19 dp[i][j] = dp[i - 1][j - 1];
20 } else {
21 int insert = dp[i][j - 1];
22 int delete = dp[i - 1][j];
23 int replace = dp[i - 1][j - 1];
24
25 dp[i][j] = 1 + ((insert < delete ? insert : delete) < replace ?
26 (insert < delete ? insert : delete) : replace);
27 }
28 }
29 }
30
31 return dp[m][n];
32}This C solution utilizes a 2D array to represent the dynamic programming table.
We begin by setting up the initial conditions for the dp array and filling it in based on whether the corresponding characters match or differ, considering the minimal operation costs of deletion, insertion, and replacement.
This approach uses recursive calls with memoization to effectively reduce the factors of redundant subproblem calculations. We use a hash map or an array to store results of previously encountered subproblems to avoid recalculating them, subsequently turning the recursive depth-first search into a memoized search.
Time Complexity: O(m * n) where m and n are lengths of word1 and word2. Each subproblem is computed once.
Space Complexity: O(m * n) for memoization storage plus recursion call stack space.
1import java.util.HashMap;
2
3
This Java solution implements a top-down recursion with memoization. The primary operation function 'helper' recursively solves the edit distance problem by considering character matches and operations separately.
Memoization is achieved by storing results of subproblems in a HashMap, uniquely keyed by the indices of remaining substrings.