[medium] 583. Delete Operation for Two Strings

문제

https://leetcode.com/problems/delete-operation-for-two-strings/

---

풀이방법

word1 에서 몇번의 알파벳 추가/삭제 작업을 거치면 word2를 만들 수 있는지 찾는 문제이다.

word1과 word2에서 연속되는 공통부분을 먼저 찾고 공통부분의 길이를 len_subseq 라고 하면,

답은 len(word1)-len_subseq 과 len(word2)-len_subseq 의 합이 된다.

공통부분을 찾는 방법은 현재까지 일치하는 길이를 dp배열에 저장하는 edit distance 방식을 사용한다. 

word1의 index(wp1)와 word2의 index(wp2) 지점까지의 가능한 가장 긴 공통부분의 길이를 dp[wp2][wp1]라고 할 때,

dp[wp2][wp1] = max(dp[wp2-1][wp1], dp[wp2][wp1-1]) 이다.

위 그림에서 파란색 화살표 참고

 

word1[wp1]와 word2[wp2]의 알파벳이 동일할 경우에만,

대각선에 저장되어있는 숫자에 1을 더한 값을 dp[wp2][wp1]에 저장된 값과 비교해서 더 큰 수를 저장한다.

위 그림에서 초록색 화살표 참고

 

그래서 최종적으로 가능한 가장 긴 공통부분의 길이는 dp[len(word2)][len(word1)] 이 된다.

아래 코드에서는 구현을 편하게 하려고 첫 행과 첫 열에 0이 전부 들어가도록 하느라 dp 사이즈를 1씩 늘리긴 했다.

시간복잡도는 O(N*M)

반응형

---

코드

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        ret = 0
        arr = [[0]*(len(word1)+1) for i in range((len(word2)+1))]
        
        for wp1 in range(1, len(word1)+1):
            for wp2 in range(1, len(word2)+1):
                arr[wp2][wp1] = max(arr[wp2][wp1-1], arr[wp2-1][wp1-1])
                if word2[wp2-1] == word1[wp1-1]:
                    arr[wp2][wp1] = max(arr[wp2][wp1], arr[wp2-1][wp1-1]+1)
        ret += abs(len(word1) - arr[len(word2)][len(word1)])
        ret += abs(len(word2) - arr[len(word2)][len(word1)])
        return ret

 

참고

유사한 문제 : 72. Edit Distance

https://leetcode.com/problems/edit-distance/