Sponsored
Sponsored
This approach is based on finding the Longest Common Subsequence (LCS) between the two given strings. Once we have the LCS, the number of deletions needed is the sum of the lengths of the two strings minus twice the length of the LCS. The LCS represents the longest sequence that both strings have in common without rearranging their order. The deletions from either string will only be those characters not present in the LCS.
Here's a step-by-step process to solve the problem:
dp where dp[i][j] represents the length of LCS of string word1[0...i] and word2[0...j].dp array using the recurrence: if word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)].Time Complexity: O(m * n), where m and n are the lengths of the two strings.
Space Complexity: O(m * n), as a 2D table is used for storing intermediate results.
1function minDistance(word1, word2) {
2 const m = word1.length;
3 const n = word2.length;
4
JavaScript implementation follows the standard dynamic programming approach via nested loops checking character equality, which helps create the LCS value in a table. By computing the adjusted length difference, it delivers the required minimum steps solution.