[Leetcode] 1143. Longest Common Subsequence

Identifying the Problem

두개의 문자열에서 공통된 가장 긴 문자열 길이를 구한다.

 

Input: text1 = "abcde", text2 = "ace" Output: 3

Explanation: 가장 긴 공통 하위 문자열은 "ace" 이므로 3을 리턴한다.

Organizing thoughts

가장 먼저 떠오른 아이디어는 긴 문자열의 기준으로 작은 문자열의 문자와 비교하며 길이를 구하는 방법이다.

하지만 이 방법은 O(n^2) 이므로 O(n)인 방법을 생각해보았다.

string관련 무네를 풀 때는, map/ dp 선에서 다 풀리기에 map으로 풀어보았다.

1. text1 과 text2의 lettermap을 만든다
2. lettermap을 비교하며 둘 중에 작은 값을 누적시킨다.ex) text1_map[‘a’] = 3 , text2_map[‘a’] = 1 이면 sum에 1을 누적
3. sum 리턴
실수 : 내가 문제를 제대로 이해하지 못했다.
text1 이 abc , text2 가 cba 라면 리턴값은 3이 아니라, 1이 되어야 한다.
즉 문자의 개수만 같아서 되는 것이 아니라, 문자의 순서도 같아야 한다.

 

하지만 내 풀이는 substring의 순서를 어겼다.

text1 : abc , text2 : cba 라면 return 값은 3이 아니라 1이 되어야 한다.

정답 풀이 / 해설
aab와 aca 비교한다 했을 때,
1) aab ac 와 2) aa aca 일 때 각각의 개수와 둘 중의 큰 값을 채택
1)aab , a 와 aa , ac 그리고 2)aa , ac 와 a , aca 일 때 각각의 개수와 둘 중의 큰 값을 채택
…. 이런 식으로 dp를 쌓아 올린다.
즉 처음 떠오르는 접근법대로 하면 된다.

Sourcecode

## 내 풀이

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        if(text1.size() == 0 || text2.size() == 0) return 0;
        
        int sum = 0;
        
        vector<int> map1(26,0);
        vector<int> map2(26,0);
        
        for(int i = 0; i<text1.size();i++)
            map1[text1[i] - 'a'] += 1;

        for(int i = 0; i<text2.size();i++)
            map2[text2[i] - 'a'] += 1;
        
        for(int i = 0; i<26; i++)
            sum += min(map1[i],map2[i]);
        
        return sum;
    }
};

## 정담 풀이 및 출처

중간에 있는 for문은 다음의 표를 보면 이해하기 쉽다.

(0)	a (0)	c (0)	e (0)
a (0)	1	1	1
b (0)	1	1	1
c (0)	1	2	2
d (0)	1	2	2
e (0)	1	2	3

Clear Concise C++ Solution, DP - LeetCode Discuss

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        
        int n = text1.size();
        int m = text2.size();
        
        if(n == 0 || m == 0)
            return 0;
        
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); //2차원 dp vector선언
        // 아무것도 없는 것과 비교하는 것은 0이므로 초기값을 0으로 설정
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; 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]);
            }
        }
        
        return dp[n][m];
    }
};

 

New things learned

dp의 목적은 가능한 모든 경우를 파악해 결과를 도출하는 것이다.
이전의 결과들의 조금의 변화가 생겨서 다음의 결과가 가능하면해당하는 모든 이전의 값들을 사용해 다음 dp를 구한다.
위 예시에서 aab와 aca를 비교하려면 aab, ac 와 aa, aca의 값을 이용하는 것 처럼 말이다.