0583. Delete Operation for Two Strings

Given two words `word1` and `word2`, return the minimum number of steps required to make `word1` and `word2` the same. In each step, you can delete one character in either string.

To implement the solution, we need to find the length of the longest common subsequence (LCS) of the two words. The minimum number of deletions required to make the two strings equal will be the sum of the lengths of both strings minus twice the length of the LCS.

The Longest Common Subsequence (LCS) is the longest sequence that appears in both given sequences in the same order but not necessarily consecutively. For example, the LCS of "sea" and "eat" is "ea", and the LCS of "abc" and "ac" is "ac".

The steps are as follows:

1. Use dynamic programming to find the LCS of `word1` and `word2`.
2. Calculate the minimum deletions required using the formula: `len(word1) + len(word2) - 2 * LCS<sub>length</sub>`.

Time Complexity: O(m * n), where m and n are the lengths of `word1` and `word2` respectively. This is because we need to fill a 2D DP table of size m * n. Space Complexity: O(m * n), for storing the DP table.

Consider `word1 = "sea"` and `word2 = "eat"`. The LCS of "sea" and "eat" is "ea", which has a length of 2. Therefore, the minimum number of deletions required is `3 + 3 - 2 * 2 = 2`.

**LCS Algorithm:

The LCS problem can be solved using dynamic programming. The idea is to build a 2D table `dp` where `dp[i][j]` represents the length of the LCS of the substrings `word1[0…i-1]` and `word2[0…j-1]`.

**Steps:

1. Initialize a 2D array `dp` of size (m+1) x (n+1), where `m` and `n` are the lengths of `word1` and `word2` respectively.
2. Iterate over each character in `word1` and `word2`.
3. If the characters match, `dp[i][j] = dp[i-1][j-1] + 1`.
4. If the characters do not match, `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`.
5. The length of the LCS will be `dp[m][n]`.

The initial setup involves defining a function to find the LCS and then using it to calculate the minimum deletions. Below is the skeleton and test setup:

/**
 * Find the minimum number of steps to make word1 and word2 the same.
 * @param {string} word1 - First word.
 * @param {string} word2 - Second word.
 * @return {number} - Minimum number of steps.
 */
function minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }

    for (let i = 0; i <= n; i++) {
        dp[0][i] = i;
    }

    console.table(dp);


    // Build the dp table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // console.log(`word1:`);
            // console.log(word1);
            // console.log(`${' '.repeat(i - 1)}^`);

            // console.log(`word2:`);
            // console.log(word2);
            // console.log(`${' '.repeat(j - 1)}^`);

            const equalChar = word1[i - 1] === word2[j - 1];
            // console.log(`equalChar = ${equalChar}`);

            if (equalChar) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
            console.table(dp);
        }
    }

    return dp[m][n];
}

// Test cases
const testCases = [
    { word1: "sea", word2: "eat", expected: 2 },
    { word1: "leetcode", word2: "etco", expected: 4 },
    { word1: "abc", word2: "def", expected: 6 },
    { word1: "", word2: "a", expected: 1 },
    { word1: "a", word2: "", expected: 1 },
    { word1: "", word2: "", expected: 0 },
];

testCases.forEach((test, index) => {
    const result = minDistance(test.word1, test.word2);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});