[LeetCode] 1143. Longest Common Subsequence

Problem Link: https://leetcode.com/problems/longest-common-subsequence/

Category: Dynamic Programming

Difficulty : Medium

Language: Python 3

---

문제 설명

text1과 text2라는 문자열 두 개가 주어집니다. 문제는 공통된 부분 문자열(common subsequence) 중에 가장 긴 것의 길이를 구하는 것입니다. 알고리즘 이론서를 보다가 등장하기도 하는 문제입니다. ㅎㅎ

최장 공통부분 문자열(Longest Common Subsequence)을 간단히 LCS라고 칭하겠습니다. LCS(A, B) 함수는 A와 B 문자열의 LCS를 출력한다고 합시다.

문제 풀이

표를 그려봅시다. 문자열은 두 개만 주어지므로 2차원 배열로 표현이 가능합니다. 행은 text1, 열은 text2로 하겠습니다. length는 미리 구해서 시간을 절약해보겠습니다.

len1 = len(text1) + 1
len2 = len(text2) + 1

 

표는 dp라는 이름으로 list comprehension을 통해 만들 수 있습니다.

먼저 list를 선언하고 반복하여 append 하는 식으로 중첩 리스트(nested list)를 만들면, 하나의 값을 수정하고 싶은데 주소값을 참조하며 타고 타고 들어가 복사본 리스트의 모든 값이 수정될 수 있으니 주의합시다!

dp = [[0 for i in range(len2)] for j in range(len1)]

	a	b	e	c	d
a
b
c

---

이제 본격적으로 dynamic programming을 해보겠습니다. 핵심은 미리 해놨던 계산을 반복하지 않겠다는 겁니다. 예시로 text1은 "abc", text2는 "abecd"가 주어졌다고 해봅시다. "ab"와 "abe"에 대한 LCS, "ab"와 "abec"에 대한 LCS는 한 번씩만 계산하겠다는 것입니다. 같은 sequence에 대해 여러 번 계산하는 것은 정말 싫습니다. 그래서 저는 LCS 정보를 까먹지 않기 위해 표에 저장해 두겠습니다. 편의상 배열의 원소 (1, 1) 부터 (len(text1), len(text2))까지 저장하기로 했습니다.

 

표의 (i, j) 원소에 text1의 1 번부터 i 번까지의 substring과 text2의 1 번부터 j 번까지의 substring에 대한 LCS 길이를 저장할 겁니다. i 번에 오기까지 i-1, i-2, ... 1번까지의 substring과 j 번에 오기까지 j-1, j-2, ... 1번까지의 substring에 대한 LCS 정보를 알아야 (i, j) 위치의 원소를 계산할 텐데 어쩌죠?

우리는 1 번까지의 substring 부터 1씩 늘려가며 순차적으로 계산을 할 것이고, 문제없이 잘 계산했다면, 1번, 2번,.. i-1번까지의 substring과 1번, 2번,... j-1번까지의 substring에 대한 LCS 정보를 잘 저장하고 있을 것입니다.

(i, j) 까지 왔다면 (i, j-1), (i-1, j), (i-1, j-1)까지의 LCS 길이 정보는 잘 계산해서 저장하고 있겠군요.

 

표의 (i, j) 칸을 채우기 위해 character 단위로 비교, 즉 text1[i-1]와 text2[j-1]를 비교해보겠습니다.

(비교를 하지 않아도 문제를 맞힐 수는 있지만, 연산이 오래 걸리게 됩니다!)

표의 첫 번째 인덱스에서 이전 인덱스를 참조할 때 0 - 1, 즉 -1 인덱스를 참조하면서 발생하는 원치않는 동작을 방지해야 합니다. 표는 1번 부터 시작했지만 text1, text2는 0번 부터 시작하기 때문에 현재 표 상의 위치 i, j에서 -1을 해줍니다.

 

만약 둘이 같다면 text1 = "ab"와 text2 = "ab"인 (2, 2) 칸을 예를 생각할 수 있습니다. 여기서는 LCS "ab"의 길이 2를 저장해야 합니다. 현재 순서의 일치하는 character를 떼어버린 (1, 1) 원소의 값을 보면 text1 = "a", text2 = "a"인 경우 LCS 길이는 1이 됩니다. 따라서 (2, 2)에는 (i-1, j-1)의 LCS "a" 길이 1에 (i, j)에서 새롭게 발견한 "b"에 대한 정보를 추가해, LCS "ab"의 길이 2를 적어줄 것입니다.

"$$%%@b"와 "@##!b"가 주어졌다고 해도 우리는 LCS("$$%%@", "@##!")의 길이에다가 1을 더해주면 됩니다. 앞 순서 (i-1, j-1)의 substring에 대한 LCS 길이를 잘 저장하고 있다면 말이죠.

if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

	a	b	e	c	d
a	1	1
b	1	?
c

 

만약 text1[i]와 text1[j]이 다르다면 (2, 3) 칸을 예로 생각해봅시다. LCS("ab", "abe") = "ab", 즉 LCS의 길이 2를 저장해야 합니다.

1. 현재 위치에서 거리 1 만큼 떨어진 값들만 볼 겁니다. 거리 2인 원소들은 거리 1 만큼 떨어진 (i-1, j), (1, j-1) 칸들을 채울 때 확인했을 겁니다.
2. (i-1, j-1) 원소, 즉 (1, 2)의 값 LCS("a", "ab")는 고려하지 않겠습니다. 이 원소보단 앞서 언급한 (i-1, j), (i, j-1) 원소들의 LCS 길이가 더 길거나 같을 것이기 때문입니다.

이제껏 저장한 값들을 보니, (2, 2)에 LCS("ab", "ab")의 길이 2와 (1, 3)에 LCS("a", "abe")의 길이 1이 저장되어 있군요.

LCS("ab", "ab")의 길이가 2로 더 길기 때문에, (2, 2)의 값을 선택하겠습니다. LCS("ab", "abe")도 변함 없이 "ab", 길이 2를 가지기 때문에 값은 그대로 가져와서 2를 써줍니다.

else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

	a	b	e	c	d
a	1	1	1
b	1	2	?
c

 

완성된 dp 표입니다. 우리가 원하는 LCS 길이인 (3, 5) 원소의 값, dp[len(text1)][len(text2)]을 리턴하면 됩니다.

 

	a	b	e	c	d
a	1	1	1	1	1
b	1	2	2	2	2
c	1	2	2	3	3

 

완성된 코드

Runtime : 428 ms

Memory Usage : 22.8 MB

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1 = len(text1) + 1
        len2 = len(text2) + 1
        dp = [[0 for i in range(len2)] for j in range(len1)]

        for i in range(1, len1):
            for j in range(1, len2):
                dp[i][j] = dp[i-1][j-1] + 1 if text1[i-1]==text2[j-1] else max(dp[i-1][j], dp[i][j-1])
                
        return dp[len1-1][len2-1]

Runtime : 697 ms

Memory Usage : 22.7 MB

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1 = len(text1) + 1
        len2 = len(text2) + 1
        dp = [[0 for i in range(len2)] for j in range(len1)]
        
        for i in range(1, len1):
            for j in range(1, len2):
                dp[i][j] = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] + int(text1[i-1]==text2[j-1]))
        
        return dp[len1-1][len2-1]