583. Delete Operation for Two Strings

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minDistance(String word1, String word2) {
        // 定义 dp[i][j] 为 word1 前 i 个字符组成的字符串和 word2 前 j 个字符组成的字符串的最大公共子序列长度
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 如果两字符相等，则子序列长度加 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minDistance(String word1, String word2) {
        // 定义 dp[i][j] 为 word1 前 i 个字符组成的字符串与 word2 前 j 个字符组成的字符串达到相同字符串的最小步数
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // 填充 dp[0][j] 为 j
        for (int j = 1; j <= word2.length(); j++) {
            dp[0][j] = j;
        }

        // 填充 dp[i][0] 为 i
        for (int i = 1; i <= word1.length(); i++) {
            dp[i][0] = i;
        }

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + 1;
                }
            }
        }

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

References

583. Delete Operation for Two Strings