PROBLEM DESCRIPTION
Given two strings str1 and str2. Return the minimum number of operations required to convert str1 to str2. The possible operations are permitted:
- Insert a character at any position of the string.
- Remove any character from the string.
- Replace any character from the string with any other character.
SOLUTION
The main logic is this:
1
2
3
4
5
6
7
8
9
10
11
// Insert a character in s1
int insert = 1 + ed(s1, s2, i, j - 1, dp);
// Remove a character from s1
int remove = 1 + ed(s1, s2, i - 1, j, dp);
// Replace a character in s1 with a character from s2
int replace = 1 + ed(s1, s2, i - 1, j - 1, dp);
// Choose the operation with the minimum cost and add one for the current operation
dp[i][j] = Math.min(insert, Math.min(remove, replace));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public int editDistance(String str1, String str2) {
int n = str1.length();
int m = str2.length();
int[][] dp = new int[n][m];
// Initialize all values in the dp array to -1 to indicate they haven't been computed yet
for (int i = 0; i < n; i++)
Arrays.fill(dp[i], -1);
// Start the recursive function to compute the edit distance from the last character of both strings
return ed(str1, str2, n - 1, m - 1, dp);
}
public int ed(String s1, String s2, int i, int j, int[][] dp) {
// If both strings are empty, no edits are required
if (i < 0 && j < 0)
return 0;
// If s1 is empty, all characters of s2 need to be inserted into s1
if (i < 0)
return j + 1;
// If s2 is empty, all characters of s1 need to be removed
if (j < 0)
return i + 1;
// If the value is already computed, use it
if (dp[i][j] == -1) {
// If the characters are the same, no edit is needed, move to the next characters
if (s1.charAt(i) == s2.charAt(j)) {
dp[i][j] = ed(s1, s2, i - 1, j - 1, dp);
} else {
// Calculate the cost of each operation: insert, remove, replace
// Insert a character in s1
int insert = ed(s1, s2, i, j - 1, dp);
// Remove a character from s1
int remove = ed(s1, s2, i - 1, j, dp);
// Replace a character in s1 with a character from s2
int replace = ed(s1, s2, i - 1, j - 1, dp);
// Choose the operation with the minimum cost and add one for the current operation
dp[i][j] = Math.min(insert, Math.min(remove, replace)) + 1;
}
}
// Return the computed value for this subproblem
return dp[i][j];
}
}