Leetcode - 1143. Longest Common Subsequence

문제

두 문자열에서 공통으로 가장 긴 subsequence를 구하라.

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

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

해결 아이디어

재귀 관계식을 해설보고 알았다. 그래도 재귀 관계식을 코드로 구현하는건 어렵지 않게 해냄. 해설보고 더 공부해야할 문제!

풀이 DP - memoization

class Solution {
    vector<vector<int>> dp;
    string t1;
    string t2;
    int recur(int i, int j) {
        if (i < 0 || j < 0)
            return 0;
        if (i == 0 && j == 0) {
            return (int)t1[i] == t2[j];
        }
        if (dp[i][j] != -1)
            return dp[i][j];
        
        if (t1[i] == t2[j]) {
            dp[i][j] = recur(i - 1, j - 1) + 1;
        } else {
            dp[i][j] = max(recur(i - 1, j), recur(i, j - 1));
        }
        return dp[i][j];
    }
public:
    int longestCommonSubsequence(string text1, string text2) {
        dp = vector<vector<int>>(1001, vector<int>(1001, -1));
        t1 = text1;
        t2 = text2;
        return recur(t1.length() - 1, t2.length() - 1);
    }
};

230306

다시 풀어봄. 해결 방법을 떠올리지 못함. 갈길이 멀구나.

class Solution {
public:
    int mem[1001][1001];
    string s1, s2;
    
    int recur(int i1, int i2) {
        if (i1 < 0 || i2 < 0)
            return 0;
        if (i1 == 0 && i2 == 0) {
            if (s1[i1] == s2[i2])
                return 1;
            else
                return 0;
        }
        if (mem[i1][i2] != -1)
            return mem[i1][i2];
        
        if (s1[i1] == s2[i2]) {
            mem[i1][i2] = recur(i1-1, i2-1) + 1;
        } else {
            mem[i1][i2] = std::max(recur(i1, i2-1), recur(i1-1, i2));
        }
        return mem[i1][i2];
            
    }
    int longestCommonSubsequence(string text1, string text2) {
        s1 = text1;
        s2 = text2;
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j < 1001; j++)
                mem[i][j] = -1;
        
        return recur(s1.size() -1, s2.size() -1);
    }
};

풀이 - DP bottom up

속도가 훨씬 빠르고 코드가 더 간결하다. mem의 사이즈가 (n+1) * (m+1) 이 되어야함에 유의.

class Solution {
public:
    string t1, t2;
    int longestCommonSubsequence(string text1, string text2) {
        int mem[1002][1002] = {0};
        t1 = text1;
        t2 = text2;
        for (int i = t1.size() - 1; i >= 0; i--) {
            for (int j = t2.size() - 1; j >= 0; j--) {
                if (t1[i] == t2[j]) {
                    mem[i][j] = mem[i+1][j+1] + 1;
                } else {
                    mem[i][j] = std::max(mem[i+1][j], mem[i][j+1]);
                }
            }
        }
        return mem[0][0];
    }
};

230325

여전히 풀이를 떠올리지 못함. 이정도면 내가 이 문제를 풀기위한 접근 과정을 이해하지 못했다는 의미. 지금까지 단순하게 풀이를 암기해서 풀었던것. 이러면 다음에 다시 볼때 또 못풀 가능성이 크다. how to think to solve 의 과정을 정확히 이해하자.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int size1 = text1.size();
        int size2 = text2.size();
        vector<vector<int>> mem(size1 + 1, vector<int>(size2 + 1, 0));

        for (int i = size1 - 1; i >= 0; i--) {
            for (int j = size2 - 1; j >= 0; j--) {
                if (text1[i] == text2[j])
                    mem[i][j] = mem[i+1][j+1] + 1;
                else
                    mem[i][j] = std::max(mem[i+1][j], mem[i][j+1]);
            }
        }   
        return mem[0][0];
    }
};