Common Sequence Problem Set Summary C++


  • 0
    F

    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;
    	}
    };
    
    

Log in to reply
 

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