[Leetcode] 1143. Longest Common Subsequence 문제풀이

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

Longest Common Subsequence - LeetCode

 

문제 내용

2개의 문자열에서 공통된 부분 문자열을 구하는 문제

 

Example 1:

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

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

 

문제 풀이

처음에는 간단하게 중복된 문자가 있는 지 table을 이용해서 풀었다.

그러나 실패했다.

이유는 index가 꼬이면 안된다.

0,3,2 이런식으로 index가 꼬인 문자열은 허용 안하는 문제였다.

 

그래서 DP를 이용해서 풀었다.

모든 부분 집합을 구해야되는데 중복된 부분이 많이 있었다.

이 부분을 값을 저장해서 빠르게 했다.

DP[i][j] = i번째 text1과 j번째 text2에서의 최대 공통 길이

 

class Solution {
public:
    int dp[1000][1000] = {0};
    
    int length(string& text1, string& text2, int i, int j) {
        if (i == text1.length() || j == text2.length())
            return 0;
        
        int& ret = dp[i][j];
        if (ret != -1)
            return ret;
        
        ret = max(length(text1, text2, i+1, j), length(text1, text2, i, j+1));
        if (text1[i] == text2[j]) {
            ret = max(ret, length(text1, text2, i+1, j+1)+1);
        } 
        return ret;
    }
    
    int longestCommonSubsequence(string text1, string text2) {
        memset(dp, -1, sizeof(dp));
        return length(text1, text2, 0, 0);
    }
};