Logo

Delete Operation for Two Strings

LeetCode의 Delete Operation for Two Strings 문제를 함께 풀어보도록 하겠습니다.

문제

두 개 문자열이 주어졌을 때, 두 개의 문자열을 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수를 구하라.

예제

Input: word1 = "sea", word2 = "eat"
Output: 2

"sea"에서 "s"를 삭제하고, "eat"에서 "t"를 삭제하면 동일하게 "ea"가 남는다. 따라서, "s", "t" 이렇게 총 2개의 글자를 삭제해야한다.

풀이 1

주어진 예제를 통해서 이 문제를 어떻게 풀 수 있을지 한번 생각해보겠습니다.

"sea""eat"의 첫 글자를 비교해보면 다르기 때문에 적어도 둘 중에 하나는 삭제를 해야한다는 것을 알 수 있습니다. 여기서 우리는 2가지 경우의 수가 생기는데요.

  1. 만약에 "sea"의 첫 번째 글자인 "s"를 삭제한다면, "ea""eat"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수가 필요할 것입니다.
  2. 만약에 "eat"의 첫 번째 글자인 "e"를 삭제한다면, "sat""at"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수가 필요할 것입니다.

우리는 삭제해야하는 최소한의 글자의 수가 필요하기 때문에 이 둘 중에 더 작은 값을 선택한 후, 어느 경우를 선택하든 1개의 글자는 삭제하는 것이기 때문에 1을 더해야 할 것입니다.

F()를 두 개의 문자열을 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수를 구하는 함수라고 한다면 첫글자가 다른 "sea""eat"의 경우 다음과 같이 계산이 됩니다.

F("sea", "eat") = 1 + min(F("ea", "eat"), F("sea", "at"))

이를 통해서 이 문제는 재귀 알고리즘으로 풀 수 있다는 것을 알 수 있습니다. 입력 값이 큰 하나의 문제를 입력 값이 작은 하위 문제 두 개의 문제로 나눠서 접근하는 전형적인 재귀 알고리즘의 모습입니다.

위의 첫 번째 경우의 수에서 "ea""eat"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자 수가 필요하다고 있는데요. 이 두 문자열을 똑같에 만들기 위해서 삭제해야하는 최소한의 글자수는 어떻게 구할까요? 이번에는 첫 글자가 동일하기 때문에 아무 것도 삭제할 필요가 없습니다.

따라서, "ea""eat"와 같이 두 문자열의 첫 글자가 같을 때는 다음과 같이 해당 문자를 그냥 무시하면 됩니다.

F("ea", "eat") = F("a", "at")

"a""at"도 첫 글자가 같으므로 동일한 경우가 해당하겠네요.

F("a", "at") = F("", "t")

"""t"를 꼬같게 만들기 위해서는 "t"만 삭제하면 됩니다. 이렇게 둘 중에 하나가 빈 문자열인 경우 다른 문자열의 모든 문자를 삭제해야합니다. 이 경우를 재귀 함수의 기저 사례(base case)로 사용할 수 있겠습니다.

"sea""eat"가 주어졌을 때, 재귀 함수가 어떻게 연쇄적으로 호출되는지를 아래와 같이 시각해볼 수 있습니다.

F("sea", "eat") => 1 + min(1, 2) => 2
        F("ea", "eat") => 1
                F("a", "at") => 1
                        F("", "t") => 1
        F("sea", "at") => 1 + min(2, 4) = 3
                F("ea", "at") => 1 + min(1, 3) => 2
                        F("a", "at") => 1
                                F("", "t") => 1
                        F("ea", "t") => 1 + min(2, 2) => 3
                                F("a", "t") => 1 + min(1, 1) = 2
                                        F("", "t") => 1
                                        F("a", "") => 1
                                F("ea", "") => 2
                F("sea", "t") => 1 + min(3, 3) = 4
                        F("ea", "t") => 1 + min(2, 2) = 3
                                F("a", "t") => 1 + min(1, 1) = 2
                                        F("", "t") => 1
                                        F("a", "") => 1
                                F("ea", "") => 2
                        F("sea", "") => 3

이 재귀 알고리즘을 코드로 구현해보겠습니다.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def dfs(i, j):
            if i == len(word1):
                return len(word2) - j
            if j == len(word2):
                return len(word1) - i
            if word1[i] == word2[j]:
                return dfs(i + 1, j + 1)
            return 1 + min(dfs(i + 1, j), dfs(i, j + 1))

        return dfs(0, 0)

첫 번째 문자열의 길이를 m, 두 번째 문자열의 길이를 n이라고 한다면, 이 풀이의 시간 복잡도는 O(2^(mn)) 입니다. 왜냐하면 재귀 호출을 할 때 마다 최악의 경우, 즉 두 문자열 간에 같은 문자가 하나도 없을 경우에는 2번씩 연쇄 호출이 일어나기 때문입니다.

이 재귀 호출 스택은 최대 두 문자열로 부터 만들 수 있는 모든 문자의 쌍만큼 깊어질 수 있기 때문에 공간 복잡도는 O(mn) 입니다.

참고로 이 풀이의 시간 복잡도는 메모이제이션(memoization) 기법을 이용하여 중복 계산을 제거하면 O(mn)로 개선할 수 있습니다.

풀이 2

위 재귀 알고리즘은 Top-down 방향으로 문제에 접근하고 있는데요. 이번에는 반대로 Bottom-up 방향으로 문제에 접근해보면 어떨까요?

즉, 빈 문자열이 주어진 경우부터 시작해서 전체 문제열이 주어진 경우까지 거슬러 올라가는 것입니다.

먼저 아주 간단한 경우에 대해서 생각해보면 좋을 것 같아요. 예를 들어, "a""ab"를 똑같게 만들기 위해서는 두 번째 문자열에서 "b" 하나만 삭제하면 되죠?

두 개의 빈 문자열이 주어졌다면 지울 글자가 자체가 없으므로 삭제 가능한 글자의 수는 0일 것입니다.

"" vs "" => 0

첫 번째 문자열은 빈 문자열로 두고 두 번째 문자열에서 첫 번째 문자를 고려하면 삭제해야 할 글자의 수는 1이 되지요.

"" vs "a" => 1

마찬가지로 두 번째 문자열에서 두 번째 문자까지 고려하면 삭제해야 할 글자의 수는 2가 됩니다.

"" vs "ab" => 2

이번에는 첫 번째 문자열에 첫 번째 문자를 추가하고, 두 번째 문자열에 빈 문자열로 놓아보면 삭제해야 할 글자의 수는 1이 됩니다.

"a" vs "" => 1

첫 번째 문자열은 그대로 두고 두 번째 문자열에서 첫 번째 문자까지 고려하면 삭제해야 할 글자의 수는 0이 됩니다.

"a" vs "a" => 0

0이 될까요? 동일해서 지울 필요가 없는 "a"를 제외하고 생각하면 위에서 이미 다뤘던 빈 문자열 두 개가 주어진 경우와 동일하게 때문입니다.

"" vs "" => 0

마지막으로 두 번째 문자열에서 두 번째 문자까지 고려하면 삭제해야 할 글자의 수는 1이 됩니다.

"a" vs "ab" => 1

1이 될까요? 두 문자열의 마지막 글자인 "a""b"는 다르기 때문에 적어도 둘중에 하나는 삭제해야 합니다.

첫 번째 문자열에서 "a"를 삭제해보면 다음 경우가 되는데 위에서 이미 다루었고요.

"" vs "ab" => 2

두 번째 문자열에서 "b"를 삭제해보면 다음 경우가 되는데 역시 위에서 이미 다루었습니다.

"a" vs "a" => 0

삭제해야하는 최소한의 글자의 수가 필요하기 때문에 이 둘 중에 더 작은 값인 0을 선택해야겠죠? 즉, 두 번째 문자열에서 "b"를 삭제하는 것이 유리하고 그래서 결과적으로 하나의 문자만 삭제하면 되는 것입니다.

이렇게 이전 단계에서 계산한 결과를 현재 단계에서 재사용이 가능하다면 다이나믹 프로그래밍(Dynamic Programing)을 적용할 수 있습니다. 지금까지 거쳐온 과정에서 규칙을 도출해보겠습니다.

  • dp[i][j]word1에서 처음 i개의 문자, word2에서 처음 j개의 문자를 똑같에 만들기 위해서 삭제해야하는 최소한의 글자 수라고 가정하면
  • word1[i - 1]word2[j - 1]이 같은 문자이면, dp[i][j]dp[i - 1][j - 1]이 된다.
  • word1[i - 1]word2[j - 1]이 다른 문자이면, dp[i][j]1 + min(dp[i - 1][j], dp[i][j - 1])이 된다.

"a""ab"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자의 수를 2차원 배열에 저장해보면 다음과 같습니다.

   _  a  b
_ [0, 1, 2]
a [1, 0, 1]

마찬가지 방법으로 문제에서 주어진 예제인 "sea""see"를 똑같게 만들기 위해서 삭제해야하는 최소한의 글자의 수를 다음과 같이 저장할 수 있습니다.

   _  e  a  t
_ [0, 1, 2, 3]
s [1, 2, 3, 4]
e [2, 1, 2, 3]
a [3, 2, 1, 2]

이 다이나믹 프로그래밍 알고리즘을 코드로 구현해볼까요?

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for i in range(len(word2) + 1):
            dp[0][i] = i
        for j in range(len(word1) + 1):
            dp[j][0] = j
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

이중 루프를 사용하고 있으므로 이 풀이의 시간 복잡도는 O(mn)이 되며, 공간 복잡도도 2차원 배열을 사용하므로 O(mn) 입니다.

풀이 3

위 다이나믹 프로그래밍 알고리즘은 조금만 더 머리를 굴려보면 2차원 배열 대신에 1차원 배열만을 사용하도록 공간 최적화가 가능합니다.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        prev = [0 for _ in range(len(word2) + 1)]

        for i in range(len(word1) + 1):
            curr = [0 for _ in range(len(word2) + 1)]
            for j in range(len(word2) + 1):
                if i == 0:
                    curr[j] = j
                elif j == 0:
                    curr[j] = i
                elif word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = 1 + min(prev[j], curr[j - 1])
            prev = curr

        return prev[len(word2)]

이 풀이의 시간 복잡도는 O(mn), 공간 복잡도는 O(n) 입니다.