Delete Operations for Two Strings

Problem

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".

Note:

• The length of given words won't exceed 500.
• Characters in given words can only be lower-case letters.

Solution

Typical Matrix DP Solution: O(n m) time, O(n m) space

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = word1.charAt(i - 1) == word2.charAt(j - 1) ? dp[i - 1][j - 1] + 1 : Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return len1 + len2 - 2 * dp[len1][len2];
    }
}

Analysis

This is a typical matrix dp solution
Since we can only delete character in either string
The problem becomes to find the longest subsequence
Hence we use typical dp solution and construct a matrix
If we find previous character equal, we update the current dp with adding 1
Otherwise, we get the bigger value from dp[i][j - 1] or dp[i - 1][j]