つの文字列の削除操作

これは一連のleetcode解決説明の一部です.あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストとmy solution post on Leetcode's forums .

Leetcode Problem #583 (Medium): Delete Operation for Two Strings

説明
にジャンプします.Solution Idea || コードJavaScript | Python | Java | C++ )

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

例:

Example 1:
Input:	word1 = "sea", word2 = "eat"
Output:	2
Explanation:	You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:
Input:	word1 = "leetcode", word2 = "etco"
Output:	4

制約

• 1 <= word1.length, word2.length <= 500
• word1 and word2 consist of only lowercase English letters.

考え
にジャンプします.Problem Description || コードJavaScript | Python | Java | C++ )
この問題は基本的に2つの単語(W 1、W 2)の間で最も長い共通部分系列(LCS)を特定するように私たちに頼みます.答えは、単語の長さとLCSの長さの間の組み合わせの違いになります.
典型的なLCS解決のために、我々はボトムアップ動的プログラミング(DP)アプローチを使用して、互いに対して各々の単語の各々の手紙を比較するために入れ子状のループを使用します(w 1 [ i ]、w 2 [ j ]).これは通常、M = W 1のサイズ( M + 1 )*( n + 1 )のDP配列を呼び出します.長さとn = w 2.長さ.LCSプロセスは、ターゲットセルの前の行と列を参照しているので、0でいっぱいのセルの余分なバッファが必要になります.DP [ i ][ j ]でDP配列の各セルは、W 1の間で見つけられる最も長いサブシーケンスを表します.substr ( 0 , i )とW 2susbtr ( 0 , j )最終的な答えはDP [ M ] [ N ]です.
DP配列が反復的に構築されているので、順番に、現在の行と最後の行(dpcurr、dplast)を繰り返すだけでO(n * m)から正常な空間の複雑さを減らすことができます.これはo ( n )にスペースの複雑さを落とすでしょう.これを行うには、必要に応じて短い単語が2つの単語をスワップすることによってNに使用されることも保証できます.

時間の複雑さ:n(n)とmは2つの単語の長さである

空間の複雑さ:O(n)は、Nが2つの語のより小さい長さです

実装
JavaScriptとJavaでは、文字列ではなく配列を繰り返し実行することが容易になりますので、最初にsplit ()またはtochararray ()という2つの単語( WA 1 , WA 2 )を指定できます.

JavaScriptコード
にジャンプします.Problem Description || Solution Idea )

var minDistance = function(W1, W2) {
    let m = W1.length, n = W2.length
    if (m < n) [W1, W2, m, n] = [W2, W1, n, m]
    let WA1 = W1.split(""), WA2 = W2.split(""),
        dpLast = new Uint16Array(n + 1),
        dpCurr = new Uint16Array(n + 1)
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) 
            dpCurr[j+1] = WA1[i] === WA2[j]
                ? dpLast[j] + 1
                : Math.max(dpCurr[j], dpLast[j+1]);
        [dpLast, dpCurr] = [dpCurr, dpLast]
    }
    return m + n - 2 * dpLast[n] 
};

Pythonコード:
にジャンプします.Problem Description || Solution Idea )

class Solution:
    def minDistance(self, W1: str, W2: str) -> int:
        m, n = len(W1), len(W2)
        if m < n: W1, W2, m, n = W2, W1, n, m
        dpLast, dpCurr = [0] * (n + 1), [0] * (n + 1)
        for c1 in W1:
            for j in range(n):
                dpCurr[j+1] = dpLast[j] + 1 if c1 == W2[j] else max(dpCurr[j], dpLast[j+1])
            dpLast, dpCurr = dpCurr, dpLast
        return m + n - 2 * dpLast[n]

Javaコード:
にジャンプします.Problem Description || Solution Idea )

class Solution {
    public int minDistance(String W1, String W2) {
        int m = W1.length(), n = W2.length();
        if (m < n) {
            String tempStr = W1;
            W1 = W2;
            W2 = tempStr;
            int tempInt = n;
            n = m;
            m = tempInt;
        }
        char[] WA1 = W1.toCharArray(), WA2 = W2.toCharArray();
        int[] dpLast = new int[n+1], dpCurr = new int[n+1];
        for (char c1 : WA1) {
            for (int j = 0; j < n; j++) 
                dpCurr[j+1] = c1 == WA2[j]
                    ? dpLast[j] + 1
                    : Math.max(dpCurr[j], dpLast[j+1]);
            int[] tempArr = dpLast;
            dpLast = dpCurr;
            dpCurr = tempArr;
        }
        return m + n - 2 * dpLast[n];
    }
}

C++コード:
にジャンプします.Problem Description || Solution Idea )

class Solution {
public:
    int minDistance(string W1, string W2) {
        int m = W1.size(), n = W2.size();
        if (m < n) swap(W1, W2), swap(n, m);
        vector<int> dpLast(n+1, 0), dpCurr(n+1, 0);
        for (char c1 : W1) {
            for (int j = 0; j < n; j++) 
                dpCurr[j+1] = c1 == W2[j]
                    ? dpLast[j] + 1
                    : max(dpCurr[j], dpLast[j+1]);
            swap(dpLast, dpCurr);
        }
        return m + n - 2 * dpLast[n];
    }
};