题解 | #NC92_LCS最长公共子序列#
最长公共子序列-II
http://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
// 构造最大公共子序列长度矩阵
vector<vector<int>> maxLen(s1.size()+1, vector<int>(s2.size()+1, 0)); // 大一圈，方便计算边界
for(int i = 1; i <= s1.size(); i++)
for (int j = 1; j <= s2.size(); j++) {
if (s1[i - 1] == s2[j - 1])
maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
else if (s1[i - 1] != s2[j - 1])
maxLen[i][j] = max(maxLen[i-1][j], maxLen[i][j-1]);
}
string res;
int i = s1.size();
int j = s2.size();
while (maxLen[i][j]) {
if (s1[i - 1] == s2[j - 1]) {
res.append(s1.substr(i - 1, 1));
i--;
j--;
}
else {
maxLen[i - 1][j] >= maxLen[i][j - 1] ? i-- : j--; // >=保证构造顺序固定
// 元素不相等但最大公共子序列长度相等时优先向上
}
}
reverse(res.begin(), res.end());
if(!res.empty())
return res;
return "-1";
}
}; 
