[LeetCode] 1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/?envType=daily-question&envId=2024-01-25

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Longest Common Subsequence

문제 유형 : 다이나믹 프로그래밍 / 재귀

문제 난이도 : Medium

 

문제

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.

 

두 문자열 text1과 text2가 주어진다. 이 둘의 가장 긴 공통 부분순열의 길이를 구하시오.

없으면 0을 반환하시오.

 

부분순열은 기존 문자열에서 순서 변경 없이 몇 글자가 지워진 문자열이다.

두 문자열의 공통 부분순열은  두 문자열이 만들 수 있는 공통의 부분순열이다.

 

 

풀이

탑다운, 바텀업의 방식 모두 쉽게 풀 수 있다.

조건은 모두 똑같다.

 

dp[i][j] = text1[i], text2[j]까지의 lcs의 최대 길이로 정한다. 

text1을 읽는 인덱스를 i, text2를 읽는 인덱스를 j라고 했을 때, 

text[i] == text[j]인 경우, dp에 카운트 1을 더할 수 있다. (lcs길이 하나 늘리기)

아니라면, dp[i][j+1]과 dp[i+1][j]중에서 최대값을 저장한다. (두 인덱스 중 하나만 늘린 것에서 더 큰 값을 가지기)

 

코드

C++

 

메모이제이션(탑-다운)

class Solution {
private:
    int n, m;
    string t1, t2;
    vector<vector<int>> dp;
public:
    int solve(int i, int j) {
    	// 인덱스 다읽으면 끝
        if(i == n || j == m) {
            return 0;
        }
        // 이미 읽은 적 있는 인덱스조합이면, 건너뛰기
        if(dp[i][j] != -1) return dp[i][j];
		
        // 같으면 lcs길이 1 추가
        if(t1[i] == t2[j]) return dp[i][j] = solve(i+1, j+1) + 1;
        // 아니라면 두 인덱스 중 하나만 올리기
        else return dp[i][j] = max(solve(i+1, j), solve(i, j+1));
    }

    int longestCommonSubsequence(string text1, string text2) {
        n = text1.size();
        m = text2.size();
        t1 = text1;
        t2 = text2;
        dp = vector<vector<int>>(n+1, vector<int>(m+1, -1));

        return solve(0, 0);
    }
};

 

 

타뷸레이션(바텀-업)

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int n = text1.size();
        const int m = text2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
            	// 같으면 길이 +1
                if(text1[i] == text2[j]) dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1);
                // 아니라면 두 인덱스중 하나만 이동한 것 중에서 더 큰것
                else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            }
        }

        return dp[n][m];
    }
};