Delete Operation for Two Strings
Medium · 1-D Dynamic Programming · Explanation and code example
Longest Common Subsequence
How it works
The characters retained in both strings after deletions form a common subsequence. Keep the longest such subsequence to minimize deletions. If its length is L, remove len(word1) - L characters from the first and len(word2) - L from the second.
Steps
- Build the LCS table over string prefixes.
- On equal characters extend the diagonal; otherwise take the larger neighboring state.
- Return both lengths minus twice the LCS length.
Complexity
- Time: O(mn).
- Space: O(mn).
Things to watch for
- Only deletions are allowed, unlike full edit distance.
- The retained characters need not be contiguous.
- Empty-string prefix rows and columns start at zero.
Python code example
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
k = self._lcs(word1, word2)
return (len(word1) - k) + (len(word2) - k)
def _lcs(self, a: str, b: str) -> int:
m = len(a)
n = len(b)
# dp[i][j] := the length of LCS(a[0..i), b[0..j))
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
C++ code example
class Solution {
public:
int minDistance(string word1, string word2) {
const int k = lcs(word1, word2);
return (word1.length() - k) + (word2.length() - k);
}
private:
int lcs(const string& a, const string& b) {
const int m = a.length();
const int n = b.length();
// dp[i][j] := the length of LCS(a[0..i), b[0..j))
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (a[i - 1] == b[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
return dp[m][n];
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.