LeetCode Weekly Contest 111 : 943. Find the Shortest Superstring

初めて本番参加。実行環境に慣れず苦戦…。
https://leetcode.com/contest/weekly-contest-111/problems/find-the-shortest-superstring/

問題

N個の文字列からなる集合Aが与えられる。全文字列を部分文字列として含む文字列のうち最短の物を答えよ。

解法

Aのうち、片方が片方の部分文字列として含まれるようなものは先に消しておこう。
以下を考える：
dp(mask, n) := Aにうちmaskに相当する要素を部分文字列として含み、かつ末尾がA[n]である文字列のうち最短の物
最終的にdp(2^N-1,*)のうち最短の物を求めたい。

この文字列の末尾に何文字か加え、さらにA[m]を含むようにすることを考える。
その場合A[n]のsuffixとA[m]のprefixができるだけ重複するようにすると、加える文字が最小化できる。
最大何文字重複するかを先に求めておくと、A[m]を末尾に含む文字列への変形が高速に行えるようになる。

int same[21][21];
string dp[1<<12][12];

class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        int x,y,i,mask,j;
        int del[12];

        sort(ALL(A));
        A.erase(unique(ALL(A)),A.end());
        int N=A.size();
        
        ZERO(del);
        FOR(x,N) FOR(y,N) if(A[x].size()<A[y].size()) {
			for(i=0;A[x].size()+i<=A[y].size();i++) {
				if(A[x]==A[y].substr(i,A[x].size())) del[x]=1;
			}
		}
		
		for(i=N-1;i>=0;i--) if(del[i]) A.erase(A.begin()+i);
		N=A.size();
		cout<<N<<endl;
		FOR(i,N) cout<<A[i]<<endl;
        FOR(x,N) FOR(y,N) if(x!=y) {
			int l=0;
			FOR(l,min(A[x].size()+1,A[y].size()+1)) if(A[x].substr(A[x].size()-l)==A[y].substr(0,l)) same[x][y]=l;
		}
		
		FOR(i,N) FOR(mask,1<<N) dp[mask][i]=string(241,'0');
		
		FOR(i,N) dp[1<<i][i]=A[i];
		for(mask=1;mask<1<<N;mask++) {
			FOR(i,N)  if((mask&(1<<i))) {
				FOR(j,N) if((mask&(1<<j))==0) {
					int l=dp[mask][i].size()+(int)A[j].size()-same[i][j];
					if(dp[mask | (1<<j)][j].size() > dp[mask][i].size()+A[j].size()-same[i][j]) {
						dp[mask | (1<<j)][j]=dp[mask][i]+A[j].substr(same[i][j]);
					}
				}
			}
		}
		
		string mi=string(241,'0');
		FOR(i,N) {
			if(mi.size()>dp[(1<<N)-1][i].size()) mi=dp[(1<<N)-1][i];
		}
		return mi;
		
		
		
    }
};

まとめ

なんかどっかで似た問題見たことがある気がする。