# Common Sequence Problem Set Summary C++

• LCS

Solution :

``````class Solution {
int longest_commmon_seq(string s1, string s2) {
int n1 = static_cast<int>(s1.size()), n2 = static_cast<int>(s2.size());
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
if (i == 0 || j == 0) 	dp[i][j] = 0;
else if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
return dp[n1][n2];
}
};
``````

LCS ---- return one possible common sequence

Solution :

``````class Solution {
string longest_commmon_seq_str(string s1, string s2) {
int n1 = static_cast<int>(s1.size()), n2 = static_cast<int>(s2.size());
int dp[n1+1][n2+1];
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
if (i == 0 || j == 0) 	dp[i][j] = 0;
else if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
int index = dp[n1][n2];
string result(index, ' ');
int i = n1, j = n2;
while (i > 0 && j > 0) {
if (s1[i-1] == s2[j-1]) {
result[index-1] = s1[i-1];
i--;  j--;  index--;
}
else if (dp[i-1][j] > dp[i][j-1]) {
i--;
}
else {
j--;
}
}
return result;
}
};
``````

LCS --- return all LCS string

Solution :

``````class Solution {
private:
int dp[100][100] = {0};
void longest_commmon_seq(string s1, string s2) {
int n1 = static_cast<int>(s1.size()), n2 = static_cast<int>(s2.size());
for (int i = 0; i <= n1; i++) {
for (int j = 0; j <= n2; j++) {
if (i == 0 || j == 0) 	dp[i][j] = 0;
else if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
}

public:
//n1 : length of s1
vector<string> longest_commmon_seq_all(string s1, string s2, int n1, int n2) {
set<string> result;
if (n1 == 0 || n2 == 0) {
result.insert("");
return result;
}
if (s1[n1-1] == s2[n2-1]) {
set<string> pre_ = longest_commmon_seq_all(s1.substr(0, n1-1), s2.substr(0, n2-1));
for (auto it : pre_) {
result.insert(it + s1[n1-1]);
}
}
else {
if (dp[n1-1][n2] >= dp[n1][n2-1])
result = longest_commmon_seq_all(s1, s2, n1-1, n2);
if (dp[n1][n2-1] >= dp[n1-1][n2]) {
vector<string> remain = longest_commmon_seq_all(s1, s2, n1, n2-1);
result.insert(remain.begin(), remain.end());
}
}
return result;
}
};

``````

LCIS : longest common increasing sub-array

Solution:

核心思想：以a1的前i个字母 跟a2的table计算一次，table的最大长度，然后更新table的值，然后遍历所有的长度i, 最终得到了最大的table[] 数组，然后取其中的最大值就是我们想要的LCIS.

如果想要返回LCIS，那么我们需要记录一个parent数组来记录所有index,然后打印出来就可以

``````class Solution {
int longest_common_increasing_seq(vector<int> a1, vector<int> a2) {
int n1 = static_cast<int>(a1.size()), n2 = static_cast<int>(a2.size());
// table[j] is going to store length of LCIS ending with arr2[j]. We initialize it as 0,
int table[n2];
for (int i = 0; i < n2; i++) table[i] = 0;
for (int i = 0; i < n1; i++) {
int cur = 0;
for (int j = 0; j < n2; j++) {
if (a1[i] == a2[j]) {
if (cur + 1 > table[j])
table[j] = cur + 1;
}
if (a1[i] > a2[j]) {
if (table[j] > cur)
cur = table[j];
}
}
}

int result = 0;
for (int i = 0; i < n2; i++)
result = max(result, table[i]);
return result;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.