[Leetcode 아주 상세한 문제풀이] 1143. Longest Common Subsequence - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 1143번 문제 Longest Common Subsequence 다.

우선 문제를 살펴보자.

 

리트코드 1143번 문제 Longest Common Subsequence 링크

Longest Common Subsequence - LeetCode

Longest Common Subsequence - LeetCode

 

 

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
 
Constraints:
1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

 

 

문제 설명

문제에 대해 간략히 살펴보자.

우선 문제에서 subsequence에 대한 정의를 하고 있는데, subsequence란 주어진 문자열에서 특정 문자를 지웠을 때 얻을 수 있는 문자열이다. 단, subsequence에 존재하는 문자들의 순서는 원래 주어진 문자열 안에서의 순서와 동일해야 한다.

따라서 문제에서 주어진 예시 1번에서 보는 것처럼, 원래 주어진 문자열이 "abcde"이고 subsequence가 맞는지 아닌지 판단하고자 하는 문자열은 "ace"일때 원래 주어진 문자열에서 b와 d를 지울 경우 ace라는 문자열을 얻을 수 있고 동시에 ace의 순서 역시 변하지 않으므로 ace는 abcde의 subsequence가 맞다는 결론을 내릴수 있다.

문제로 다시 돌아와 text1과 text2 라는 두 개의 문자열이 주어진다. 이때 text1과 text2의 문자열 중 공동으로 존재하는 길이가 가장 긴 subsequence의 길이를 찾아내는 것이 문제의 목적이다.

예를 들어 문제에서 주어진 예시 1번에서처럼 "abcde"와 "ace"라는 문자열이 주어졌을 때 공동으로 존재하는 subsequence는 "ace"임을 알 수 있고, 이때 그 길이는 3이기 때문에 3을 리턴하면 된다. 만약 공동으로 존재하는 subsequence가 존재하지 않는다면 0을 리턴한다.

이제 문제를 풀어보자. 

 

 

문제 접근법

이 문제의 접근법은 여러가지 일 수 있지만 우리는 2D array를 만들어 해결해보자.

간단히 말해서 주어진 두 개의 문자열을 하나하나 비교해 보는데,

2차원 배열을 하나 만들어 common subsequence가 몇 개인지 기록할 수 있다.

 

문제에서 주어진 예시 1번 처럼 "abcde" 와 "ace"라는 문자열이 주어졌다고 생각해보자.

그리고 위와 같이 0으로 초기화된 2차원 배열을 하나 만들어 보자.

이때 2차원 배열의 크기는 (문자열1 길이 + 1) * (문자열2 길이 + 1)로 만든다.

이때 첫 행과 열에 위치한 0 값들은 common subseuqence를 카운트 하기 위해 0으로 초기화 한 것이다.

앞서 애기한대로 우리는 문자열을 하나씩 비교해나가는데

우선 첫번재 문자열 abcde에서 첫번째 문자 a와 두번째 문자열 ace에서 첫번째 문자 a를 비교해 보자.

이 경우 두 문자가 일치하기 때문에 2차원 배열에서 해당 셀을 1로 업데이트 해준다. 

 

그 후 첫번째 문자열에서 a와 두번째 문자열에서 두번째 문자 c를 비교해준다.

이때는 a와 c가 다른 문자이기 때문에 두 가지 옵션을 고려해 봐야 한다.

i) 첫번째 문자열에서 해당 문자를 건너 뛰고 탐색 계속하기

이 경우 첫번째 문자열에서 a를 건너뛰면 c와 비교할 대상이 없기 때문에,

결국 초기값으로 설정한 0 (노란색)을 해당 셀에 업데이트 한다.

 

ii) 두번째 문자열에서 해당 문자를 건너 뛰고 탐색 계속하기

이 경우 두번째 문자열에서 c를 건너뛰면 결국 첫번째 문자열에서 a와 두번째 문자열에서 a와 비교하는 것이 되기 때문에,

이 경우 첫번째 문자열에서 a와 두번째 문자열에서 a를 비교한 값(노란색)을 해당 셀에 업데이트 한다. 

 

그리고 가장 중요한 부분은 두 문자열에서 공동으로 가지고 있는 subsequence가 다시 나타나는 지점이다.

첫번째 문자열에서 c와 두번째 문자열에서 c가 나오는 지점에 이르게 되면

각 문자열에서 c에 이르기 전까지 탐색한 문자열

즉, 첫번째 문자열에서 ab와 두번째 문자열에서 a 이 둘 사이의 common subsequence 길이에 1을 더한것이

바로 c를 포함했을 때 common subsequene이 길이가 된다. 

 

따라서 첫번째 문자열에서 ab와 두번째 문자열에서 a 사이의 common subsequence의 길이 (=1, 노란색)에

1을 더해 아래와 같이 해당 셀을 2로 업데이트 해준다. 

 

이 과정을 반복하다 보면 결국 아래와 같은 2차원 배열을 얻을 수 있고

우리가 알고자 하는 두 문자열 abcde롸 ace의 common subsequence의 길이는 3임을 알 수 있다.

 

 

문제 풀이

이제 코드를 한 번 살펴보자.

두 문자열을 입력받을 함수를 정의해 준다 (line 1)

그리고 2차원 배열을 만들기 위해여 입력된 문자열 길이를 확인한다 (line 2)

앞서 설명한대로 common subsequence의 길이가 0인 경우를 고려해

크기가 (m+1) * (n+1) 인 2차원 배열을 만들어 준다 (line 5)

그 후 double for loop를 이용하여 입력된 문자열의 문자열을 하나하나 탐색하는데 (line 7-8)

 앞서 설명한대로 비교하는 문자열이 서로 같다면 (line 9)

각 문자열의 바로 직전 문자열들의 common subsequence 길이에 1을 더해준다 (line 10)

만약 비교하는 문자열이 서로 다르다면 두 가지 옵션이 있는데,

앞서 설명한대로 첫번째 문자열에서 해당 문자를 건너 뛰었을 때 common subsequence 길이나

혹은 두번째 문자열에서 해당 문자를 건너 뛰었을 때 common subsequence의 길이 중

더 긴 것을 선택하여 해당 셀을 업데이트 해준다(line 12)

최종적으로 우리가 구하고자 하는것은 common subsequence 중 길이가 가장 긴 것의 길이이므로

입력된 문자열 마지막 문자에 해당하는 dp[m][n]을 리턴해주면된다.

 

 

문제 풀이 코드

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    
    # Create a 2D table to store the length of the longest common subsequence
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            print("i= ", i)
            print("j= ", j)
            print("dp= ", dp)
            print("--------------")
    return dp[m][n]
 
# Example usage:
text1 = "abcde"
text2 = "ace"
result = longestCommonSubsequence(text1, text2)
print(result)  # Output: 3