[Leetcode] 1143. Longest Common Subsequence

1. 링크

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

Longest Common Subsequence - LeetCode

 

 

2. 키포인트

dp를 사용하여 현재 text1[i]와 text2[j]의 common subsequence의 길이를 업데이트한다

dp는 2차원 int 배열로 선언하고, 크기는 dp[text1.size()+1][text2.size()+1]로 하고 초기값은 0으로 설정한다

 

예를 들어 text1 = "aaaaa", text2="aaa"이라면 2차원 dp 배열의 사이즈는 dp[6][4]가 된다.

더블 for문의 i,j의 초기값은 1로 한다.

 

text1[i-1] == text2[j-1]라면 dp[i][j] = dp[i-1][j-1] + 1가 되고

그렇지 않다면 dp[i][j] 는 max(dp[i-1][j], dp[i][j-1])로 업데이트 해준다

 

for문을 다 돌고 dp를 출력해보면

0 0 0 0

0 1 1 1

0 1 2 2

0 1 2 3

0 1 2 3

0 1 2 3

배열의 가장 끝 값인 dp[5][3]에 있는게 정답이다

 

 

3. solution

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                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]);
                }
            }
        }
        for(auto i : dp){
            for(auto j : i){
                cout << j << " ";
            }cout<<endl;
        }

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