1143. Longest Common Subsequence

 

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

 

입력이 아래와 같을 때 

text1 = "abcde", text2 = "ace"

	a	b	c	d	e
a	1	1	1	1	1	a -> ace
c	1	1	2	2	2	c -> ace
e	2	2	2	2	3	e -> ace

 

Source

class Solution {
public:
    int dp[1001][1001];
    int longestCommonSubsequence(string text1, string text2) {
        int sol = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }

                sol = max(sol, dp[i][j]);
            }
        }

        return sol;
    }
};