-
Notifications
You must be signed in to change notification settings - Fork 0
/
1092. Shortest Common Supersequence.cpp
62 lines (49 loc) · 1.62 KB
/
1092. Shortest Common Supersequence.cpp
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
// -----Approach: Tabulation ------------------------------------------------------------
/*
Problem Link: https://leetcode.com/problems/shortest-common-supersequence/
Time: 31 ms (Beats 48.93%), Space: 12.8 MB (Beats 60.38%)
*/
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
int n= str1.size();
int m= str2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=0; i<=n; i++) dp[i][0]= 0;
for(int j=0; j<=m; j++) dp[0][j]= 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(str1[i-1] == str2[j-1]) dp[i][j]= 1 + dp[i-1][j-1];
else dp[i][j] = max( dp[i-1][j], dp[i][j-1] );
}
}
cout<<n + m - dp[n][m];
string ans="";
int i= n, j= m;
while( i>0 && j>0 ){
if(str1[i-1] == str2[j-1]){
ans+= str1[i-1];
i--;
j--;
}
else if(dp[i-1][j] > dp[i][j-1]){ // upward movement, so we take the ith character from the str1
ans+= str1[i-1]; // use dry run to understand
i--;
}
else{
ans+= str2[j-1];
j--;
}
}
while(i>0){
ans+= str1[i-1];
i--;
}
while(j>0){
ans+= str2[j-1];
j--;
}
reverse(ans.begin(), ans.end()); // we are doing it in the reverse order, so the ans would be reversed string
return ans;
}
};