Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1143. Longest Common Subsequence

---

參考資訊：
https://algo.monster/liteproblems/1143
https://www.cnblogs.com/grandyang/p/14230663.html
http://mirlab.org/jang/books/dcpr/dpLcs.asp?title=8-2%20Longest%20Common%20Subsequence&language=chinese

題目：


提示：


解答：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int t1_size = text1.size();
        int t2_size = text2.size();
        vector<vector<int>> q(t1_size + 1, vector<int>(t2_size + 1, 0));

        for (int i = 1; i <= t1_size; ++i) {
            for (int j = 1; j <= t2_size; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    q[i][j] += q[i - 1][j - 1] + 1;
                } else {
                    q[i][j] = max(q[i-1][j], q[i][j - 1]);
                }
            }
        }

        return q[t1_size][t2_size];
    }
};