题解 | #最长公共子序列(二)#

public:
	/**
	* longest common subsequence
	* @param s1 string字符串 the string
	* @param s2 string字符串 the string
	* @return string字符串
	*/
	string LCS(string s1, string s2) {
		vector<string> s(s2.size() + 1, "");
		for (int i = 0; i < s1.length(); i++) {
			string prev = s[0];
			for (int j = 0; j < s2.length(); j++) {
				string cur;
				if (s1[i] == s2[j]) { // 匹配字符
					cur = prev + s2[j]; // 上一个拼接 新字符
				}
				else { // 不匹配时
					if (s[j].size() > s[j + 1].size()) {
						cur = s[j];
					}
					else {
						cur = s[j + 1];
					}
				}
				prev = s[j + 1];
				s[j + 1] = cur;
			}
			//for (auto n : s) {
			//	cout << n << " ";
			//}
			//cout << i << " " << endl;
			//cout << endl;
		}
		return (s[s2.size()].size() == 0) ? "-1" : s[s2.size()];
	}
};