Delete Operation for Two Strings, by LeetCode: a variation of edit distance via DP
Problem is this one: https://leetcode.com/problems/delete-operation-for-two-strings/:
This is a variation of the classic String Edit Distance problem, whose solution is one of the iconic Dynamic Programming solutions. Knowing that this is a variation, all it is needed is a paper (or whiteboard) and try few variations to understand the logic: having a distance matrix where each element distance[i,j] represents the min distance when comparing word1[0..i] and word2[0..j]. The fun part is to figure out the logic of how to update distance[i,j] depending on whether word1[i] is equal or not to word2[j]. You kind of figure that our with few examples. Here is the raw whiteboard that I used, and on the side is my dog closely paying attention to my explanation. Code is down below, cheers, Marcelo.
public class Solution
{
public int MinDistance(string word1, string word2)
{
int[,] distance = new int[word1.Length + 1, word2.Length + 1];
distance[0, 0] = 0;
for (int r = 1; r <= word1.Length; r++) distance[r, 0] = r;
for (int c = 1; c <= word2.Length; c++) distance[0, c] = c;
for (int r = 1; r <= word1.Length; r++)
{
for (int c = 1; c <= word2.Length; c++)
{
if (word1[r - 1] == word2[c - 1])
{
distance[r, c] = distance[r - 1, c - 1];
}
else
{
distance[r, c] = Math.Min(distance[r - 1, c], distance[r, c - 1]) + 1;
}
}
}
return distance[word1.Length, word2.Length];
}
}
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Example 1:
Input: "sea", "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
This is a variation of the classic String Edit Distance problem, whose solution is one of the iconic Dynamic Programming solutions. Knowing that this is a variation, all it is needed is a paper (or whiteboard) and try few variations to understand the logic: having a distance matrix where each element distance[i,j] represents the min distance when comparing word1[0..i] and word2[0..j]. The fun part is to figure out the logic of how to update distance[i,j] depending on whether word1[i] is equal or not to word2[j]. You kind of figure that our with few examples. Here is the raw whiteboard that I used, and on the side is my dog closely paying attention to my explanation. Code is down below, cheers, Marcelo.
{
public int MinDistance(string word1, string word2)
{
int[,] distance = new int[word1.Length + 1, word2.Length + 1];
distance[0, 0] = 0;
for (int r = 1; r <= word1.Length; r++) distance[r, 0] = r;
for (int c = 1; c <= word2.Length; c++) distance[0, c] = c;
for (int r = 1; r <= word1.Length; r++)
{
for (int c = 1; c <= word2.Length; c++)
{
if (word1[r - 1] == word2[c - 1])
{
distance[r, c] = distance[r - 1, c - 1];
}
else
{
distance[r, c] = Math.Min(distance[r - 1, c], distance[r, c - 1]) + 1;
}
}
}
return distance[word1.Length, word2.Length];
}
}
Very nice, Marcelo! It's possible to improve this solution by reducing the space complexity which is O(N^2) in your case. If you look at the access pattern you'll notice that you're actually using only 2 rows - current and previous, hence solution can be something like:
ReplyDeleteclass Solution {
public:
int minDistance(const string& word1, const string& word2) {
vector prev(word2.size()+1);
vector current(word2.size()+1);
for (int j = 0; j <= word2.size(); ++j) prev[j] = j;
for (int i = 1; i <= word1.size(); ++i) {
current[0] = i;
for (int j = 1; j <= word2.size(); ++j) {
current[j] = word1[i-1] == word2[j-1] ? prev[j-1] : 1 + min(current[j-1], prev[j]);
}
swap(current, prev);
}
return prev[word2.size()];
}
};
Cheers,
Taras
and for those who don't like using anything but arrays:
Deleteclass Solution {
public:
int minDistance(const string& word1, const string& word2) {
int d[2][word2.size()+1];
int prev = 0;
int current = 1;
for (int j = 0; j <= word2.size(); ++j) d[prev][j] = j;
for (int i = 1; i <= word1.size(); ++i) {
d[current][0] = i;
for (int j = 1; j <= word2.size(); ++j) {
d[current][j] = word1[i-1] == word2[j-1] ? d[prev][j-1] : 1 + min(d[current][j-1], d[prev][j]);
}
swap(current, prev);
}
return d[prev][word2.size()];
}
};
A video explanation: https://youtu.be/-wxbv5l3Poc
ReplyDelete