LeetCode Weekly Contest 141 : 1092. Shortest Common Supersequence

これは8ptもあるかなぁ…？
https://leetcode.com/contest/weekly-contest-141/problems/shortest-common-supersequence/

問題

2つの文字列S,Tが与えられる。
部分列としてS,Tを持つような文字列のうち、最短の物を求めよ。

解法

解の文字列長は|S|+|T|-|LCS(S,T)|になる。
LCSと同じようにDPして復元すればよい。

int dp[1010][1010];
int from[1010][1010];

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int A=str1.size();
        int B=str2.size();
        
        int a,b;
        FOR(a,A+1) FOR(b,B+1) dp[a][b]=101010;
        dp[0][0]=0;
        FOR(a,A+1) {
			FOR(b,B+1) {
				if(a==A&&b==B) continue;
				if(a<A && b<B && str1[a]==str2[b]) {
					if(dp[a+1][b+1]>dp[a][b]+1) {
						dp[a+1][b+1]=dp[a][b]+1;
						from[a+1][b+1]=2;
					}
				}
				if(b<B && dp[a][b+1]>dp[a][b]+1) {
					dp[a][b+1]=dp[a][b]+1;
					from[a][b+1]=1;
				}
				if(a<A && dp[a+1][b]>dp[a][b]+1) {
					dp[a+1][b]=dp[a][b]+1;
					from[a+1][b]=0;
				}
			}
		}
        
        a=A,b=B;
        string R;
        while(a||b) {
			if(from[a][b]==0) {
				a--;
				R.push_back(str1[a]);
			}
			else if(from[a][b]==1) {
				b--;
				R.push_back(str2[b]);
			}
			else {
				a--;
				b--;
				R.push_back(str1[a]);
			}
		}
		reverse(ALL(R));
		return R;
        
    }
};

まとめ

BiWeeklyよりptだけ見ると難しいのか。