Leetcode -583- Delete two strings

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 identical, each step removing one character from either string.

Example:

Input: “sea”, “eat” Output: 2 Explanation: The first step changes “sea” to “EA “, the second step changes “eat” to” EA”

Tip:

The given word is not more than 500 in length. The characters in a given word contain only lowercase letters.

Idea 1: sequence DP+LCS

• It’s easy to turn this into a problem of finding the longest common subsequence
• The last thing that comes back is n- Max +m- Max
• N and m are two string lengths
• Max represents the length of the subsequence
• Dp [I][j] represents the longest common subsequence of I bits before the first string and j bits before the second string
• The process of transfer can be determined by the judgment relation of S1 [I] S2 [J]
  • If s1[I] = s2[j] dp[I][j] = DP [i-1][J-1] +1
  • Dp [I][j] = Max (dp[I][j]+1, DP [I][j-1]+1)

public int minDistance(String word1, String word2) {
            int m = word1.length(), n = word2.length();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); }}}return m - dp[m][n] + n - dp[m][n];
        }

Copy the code

• Time complexity O(m* N)
• Space complexity O(m* N)

Idea 2: Sequence DP

• The second option is a more straightforward definition of DP
• Dp [I][j] represents the number of operations required for the first I bits of a string and the first J bits of a second string to form the same string
• Dp [0] = I dp[0][j] = j
• The transfer equation is also divided into two cases
  • If s1[I] = s2[j] dp[I][j] = dp[i-1][J-1]
  • Otherwise,dp[I][J] = min(DP [i-1][J]+1, DP [I][J-1]+1)+1

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; 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 - 1][j], dp[i][j - 1]) + 1; }}}return dp[m][n];
}
Copy the code

• Time complexity O(m* N)
• Space complexity O(m* N)