솔루션: 두 문자열에 대한 삭제 작업

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #583(중간): 두 문자열에 대한 삭제 작업

설명:

(이동: 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++ )

이 문제는 기본적으로 두 단어(W1, ​​W2) 사이의 가장 긴 공통 부분 시퀀스(LCS)를 식별하도록 요청합니다. 그러면 답은 단어의 길이와 LCS의 길이 간의 결합된 차이입니다.

일반적인 LCS 솔루션의 경우 상향식 동적 프로그래밍(DP) 접근 방식을 사용하고 중첩 루프를 사용하여 각 단어의 각 문자를 서로 비교합니다(W1[i], W2[j]). 이것은 일반적으로 (m + 1) * (n + 1) 크기의 DP 배열을 요구합니다. 여기서 m = W1.length 및 n = W2.length입니다. LCS 프로세스는 대상 셀의 이전 행과 열을 참조하므로 0으로 채워진 셀의 추가 버퍼가 필요합니다. dp[i][j]에 있는 DP 배열의 각 셀은 W1.substr(0,i)와 W2.susbtr(0,j) 사이에서 발견된 가장 긴 하위 시퀀스를 나타냅니다. 그러면 최종 답은 dp[m][n]이 됩니다.

DP 배열이 반복적으로 구축되기 때문에 순서대로 반복하면서 현재 행과 마지막 행(dpCurr, dpLast)만 유지하여 일반 공간 복잡성을 O(N * M)에서 줄일 수 있습니다. 이것은 공간 복잡도를 O(N)으로 떨어뜨릴 것입니다. 이렇게 하면 필요한 경우 두 단어를 교환하여 N에 더 짧은 단어가 사용되도록 할 수도 있습니다.

시간 복잡도: O(N * M) 여기서 N과 M은 두 단어의 길이입니다

.

공간 복잡도: O(N) 여기서 N은 두 단어 중 작은 단어의 길이입니다

.

구현:

Javascript와 Java는 문자열보다 배열을 통해 반복적으로 반복하는 것이 더 쉽다는 것을 알게 될 것이므로 처음에는 두 단어(WA1, WA2)를 split() 또는 toCharArray() 할 수 있습니다.

자바스크립트 코드:

(이동: 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] 
};

파이썬 코드:

(이동: 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]

자바 코드:

(이동: 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];
    }
};