LeetCode/1092.shortest-common-supersequence.cpp at master · CSUwangj/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
 * @lc app=leetcode id=1092 lang=cpp
 *
 * [1092] Shortest Common Supersequence
 */

// @lc code=start
template<typename T>
std::ostream& operator<<(std::ostream &out, const std::vector<T> &v) {
  if(v.size() == 0) {
    out << "[]" << std::endl;
    return out;
  }
  out << '[' << v[0];
  for(int i = 1; i < v.size(); ++i) {
    out << ", " << v[i];
  }
  out << ']';
  return out;
}
class Solution {
public:
  string shortestCommonSupersequence(string str1, string str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    vector<vector<string>> dp(2, vector<string>(len2 + 1));
    for(int i = 1; i <= len2; ++i) {
      dp[0][i] = str2.substr(0, i);
    }

    for(int i = 0; i < len1; ++i) {
      int parity = i & 1;
      dp[parity ^ 1][0] = str1.substr(0, i + 1);
      for(int j = 0; j < len2; ++j) {
        if(str1[i] == str2[j]) {
          dp[parity ^ 1][j + 1] = dp[parity][j];
          dp[parity ^ 1][j + 1].push_back(str1[i]);
        } else {
          if(dp[parity ^ 1][j].length() < dp[parity][j + 1].length()) {
            dp[parity ^ 1][j + 1] = dp[parity ^ 1][j];
            dp[parity ^ 1][j + 1].push_back(str2[j]);
          } else {
            dp[parity ^ 1][j + 1] = dp[parity][j + 1];
            dp[parity ^ 1][j + 1].push_back(str1[i]);
          }
        }
      }
    }

    return dp[len1 & 1].back();
  }
};

// Accepted
// 49/49 cases passed (249 ms)
// Your runtime beats 6 % of cpp submissions
// Your memory usage beats 5.13 % of cpp submissions (35.8 MB)
// @lc code=end