[Leetcode] 1143. Longest Common Subsequence - Java

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

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.

---

풀이

풀이 과정

주어진 두 문자열에서 최장 공통 부분 문자열의 길이를 구하는 문제이다.
최장 증가 부분 수열과 마찬가지로 일치하는 문자열이 연속할 필요는 없다.
예를 들어 "ace"와 "abcde" 최장 공통 부분 문자열을 찾아보면 아래와 같다.

• [a, c, e]
• [a, b, c, d, e]

두 문자열의 각 인덱스별로 탐색 데이터를 저장하기 위해 2차원 배열을 선언하고 각 문자끼리 비교하며 값을 탐색한다.

각 배열의 인덱스가 0일 때는 공통 부분 문자열의 길이가 0이므로 0으로 마진설정되어 있다고 생각한다.

int answer = 0;

// 탐색 데이터를 저장할 배열
// int[첫 번째 문자열의 인덱스][두 번째 문자열의 인덱스]
int[][] dp = new int[text1.length() + 1][text2.length() + 1];

// 각각의 문자를 비교하며 탐색
// 0번 인덱스의 값은 0으로 마진 설정
for(int i = 1; i <= text1.length(); i++){
    for(int j = 1; j <= text2.length(); j++){
       
    }
}

 

비교할 두 문자가 같은 경우에는 현재 탐색중인 두 문자를 제외한 두 문자열의 최장 부분 수열 값을 현재 인덱스에 저장하고, 비교할 두 문자가 다른 경우에는 현재 탐색중인 두 문자를 제외한 두 문자열의 최장 부분수열 값 중 최대값을 현재 인덱스에 저장한다.

// 두 문자가 같은 경우
if(text1.charAt(i - 1) == text2.charAt(j - 1)){
    // 현재 탐색 문자를 제외한 두 문자열의 최장 부분 수열 값
    // ex) "abc"와 "ac" -> "ab"와 "a"의 최장 부분 수열 값
    dp[i][j] = dp[i - 1][j - 1] + 1;
}
// 두 문자가 다른 경우
else {
    // 현재 탐색 문자를 포함한 두 문자열의 최장 부분수열 값 중 최대값
    // ex) "abc"와 "ad" -> "abc"와 "a", "ab"와 "ad"의 최장 부분 수열 값 중 최대값
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}

 

최종 탐색한 결과값을 반환한다.

// 최종 탐색 결과를 반환
return dp[text1.length()][text2.length()];

 

LCS를 구하는 방법은 아래 블로그에 그림으로 너무 이해하기 쉽도록 정리가 잘 되어있어 해당 글을 참고하여 풀이하였다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

---

최종 코드

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int answer = 0;

        // 탐색 데이터를 저장할 배열
        // int[첫 번째 문자열의 인덱스][두 번째 문자열의 인덱스]
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        // 각각의 문자를 비교하며 탐색
        // 0번 인덱스의 값은 0으로 마진 설정
        for(int i = 1; i <= text1.length(); i++){
            for(int j = 1; j <= text2.length(); j++){
                // 두 문자가 같은 경우
                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
                    // 현재 탐색 문자를 제외한 두 문자열의 최장 부분 수열 값
                    // ex) "abc"와 "ac" -> "ab"와 "a"의 최장 부분 수열 값
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                // 두 문자가 다른 경우
                else {
                    // 현재 탐색 문자를 포함한 두 문자열의 최장 부분수열 값 중 최대값
                    // ex) "abc"와 "ad" -> "abc"와 "a", "ab"와 "ad"의 최장 부분 수열 값 중 최대값
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 최종 탐색 결과를 반환
        return dp[text1.length()][text2.length()];
    }
}

---