LeetCode/1092.shortest-common-supersequence.WA.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
59
60
61
62
63
64
/*
 * @lc app=leetcode id=1092 lang=cpp
 *
 * [1092] Shortest Common Supersequence
 */

// @lc code=start
class Solution {
  string LCS(string str1, string str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    vector<vector<string>> dp(2, vector<string>(len2 + 1));

    for(int i = 0; i < len1; ++i) {
      int parity = i & 1;
      for(int j = 0; j < len2; ++j) {
        if(str1[parity] == 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];
          } else {
            dp[parity ^ 1][j + 1] = dp[parity][j + 1];
          }
        }
      }
    }
    return dp[len1 & 1].back();
  }
public:
  string shortestCommonSupersequence(string str1, string str2) {
    string lcs = LCS(str1, str2);
    int pos1 = 0;
    int pos2 = 0;
    int len1 = str1.length();
    int len2 = str2.length();
    string answer;
    for(auto c : lcs) {
      while(pos1 < len1 && str1[pos1] != c) {
        answer.push_back(str1[pos1]);
        pos1 += 1;
      }
      while(pos2 < len2 && str2[pos2] != c) {
        answer.push_back(str2[pos2]);
        pos2 += 1;
      }
      answer.push_back(c);
      pos1 += 1;
      pos2 += 1;
    }
    while(pos1 < len1) {
      answer.push_back(str1[pos1]);
      pos1 += 1;
    }
    while(pos2 < len2) {
      answer.push_back(str2[pos2]);
      pos2 += 1;
    }

    return answer;
  }
};
// @lc code=end