[Leetcode][583] Delete Operation for Two Strings

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

---

 

문자열 word1, word2 가 주어질 때, 두 문자열을 같게 만들게하기 위해 최소 몇 개의 문자를 삭제해야하는지 구해라.

---

최장공통부분수열(LCS; Longest Common Subsequence)로 풀었다.

word1, word2 문자열의 문자들을 모두 탐색하면서 dp[i][j] (word1[0~i-1], word2[0~j-1]의 최장 공통부분수열 길이)를 세팅한다.

for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        if(word1[i-1] == word2[j-1]) 
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }    
}

word1, word2 문자열의 길이를 N, M이라 하면 dp[N][M]이 word1, word2가 동일하게 만들 수 있는 최장길이의 문자길이다.

정답은 삭제해야 하는 문자개수이기 때문에 word1을 dp[N][M] 길이로 만들기 위한 길이(N - dp[N][M]) + word2를 dp[N][M] 길이로 만들기 위한 길이(M - dp[N][M])가 정답이 된다.

 

시간복잡도는 O(NM). 공간복잡도 또한, O(NM).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/583.%20Delete%20Operation%20for%20Two%20Strings.cpp