NC92 #最长公共子序列#
最长公共子序列
http://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
第一步,通过动态规划找到最长公共子序列长度,并构建dp
数组:dp[i][j]
:s1[i]
和s2[j]
为止的最长公共子序列的长度。dp[0][0] = s1[0] == s2[0]
dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0]
dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1]
dp[i][j] = dp[i - 1][j - 1] + 1, s1[i] == s2[j]
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]), s1[i] != s2[j]
第二步,根据dp
反推最长公共子序列内容。
class Solution { public: string LCS(string s1, string s2) { if(s1.empty() || s2.empty()) return "-1"; int len1 = s1.size(), len2= s2.size(); int dp[len1][len2]; dp[0][0] = s1[0] == s2[0]; for(int i = 1; i < len1; i++) dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0]; for(int i = 1; i < len2; i++) dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1]; for(int i = 1; i < len1; i++) { for(int j = 1; j < len2; j++) { 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]); } } string ans = ""; for(int i = len1 - 1, j = len2 - 1; i >= 0 && j >= 0;) { if(s1[i] == s2[j]) { ans += s1[i]; i--, j--; } else if(j == 0 || dp[i - 1][j] > dp[i][j - 1]) i--; else if(i == 0 || dp[i][j - 1] >= dp[i - 1][j]) j--; } reverse(ans.begin(), ans.end()); return ans.size() == 0 ? "-1" : ans; } };