583. Delete Operation for Two Strings

 一刷 06/2022

Version #1 DP with 2D array

一个写错的地方就是当i == 0 || j == 0的时候，dp[i][j]等于不为0的那个substring的长度，因为需要全部删掉才能匹配

Time O(MN)

Space O(MN)

Runtime: 17 ms, faster than 43.26% of Java online submissions for Delete Operation for Two Strings.

Memory Usage: 47.2 MB, less than 34.52% of Java online submissions for Delete Operation for Two Strings.

class Solution {

    public int minDistance(String word1, String word2) {

        // dp[i][j] - number of operations to make word1[0, i) and word2[0, j) the same

        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]

        // otherwise dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1

        for (int i = 0; i <= word1.length(); i++) {

            for (int j = 0; j <= word2.length(); j++) {

                if (i == 0) {

                    dp[i][j] = j;

                    continue;

                }

                if (j == 0) {

                    dp[i][j] = i;

                    continue;

                }

                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {

                    dp[i][j] = dp[i - 1][j - 1];

                } else {

                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);

                }

            }

        }

        return dp[word1.length()][word2.length()];

    }

}

Version #2 DP with optimized memory usage

Time O(MN)

Space O(M) - M is the length of word2

If we want to make space O(min{M, N}) we could switch word1 and word2 and always use the shorter length

Runtime: 13 ms, faster than 73.06% of Java online submissions for Delete Operation for Two Strings.

Memory Usage: 42.1 MB, less than 99.71% of Java online submissions for Delete Operation for Two Strings.

class Solution {

    public int minDistance(String word1, String word2) {

        // dp[i][j] - number of operations to make word1[0, i) and word2[0, j) the same

        int[][] dp = new int[2][word2.length() + 1];

        // if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1]

        // otherwise dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1

        for (int i = 0; i <= word1.length(); i++) {

            for (int j = 0; j <= word2.length(); j++) {

                if (i == 0 || j == 0) {

                    dp[i % 2][j] = i + j;

                    continue;

                }

                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {

                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1];

                } else {

                    dp[i % 2][j] = 1 + Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);

                }

            }

        }

        return dp[word1.length() % 2][word2.length()];

    }

}