Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 28

Description

**Shortest Common Supersequence **

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

Solution

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)