Common Sequence Problem Set Summary C++
fight.for.dream
609

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;
	}
};
Comments (0)