[algo] timeline algorithm
#include <iostream> #include <string> #include <vector> using namespace std; class Solution { public: string shortestCommonSupersequence(string a, string b) { int m = a.size(); int n = b.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) continue; if (a[i-1] == b[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } int i = m; int j = n; string res; while (i > 0 && j > 0) { if (a[i-1] == b[j-1]) { res += a[i-1]; --i; --j; } else { if (dp[i-1][j] < dp[i][j-1]) { res += b[--j]; } else { res += a[--i]; } } } while (i > 0) res += a[--i]; while (j > 0) res += b[--j]; reverse(res....