C++ solution in less than 30 lines
This solution is less than 30 lines if comments are excluded.\nInstead of an int dp matrix, I use string dp matrix directly. Therefore the reconstruction is a l
This solution is less than 30 lines if comments are excluded.\nInstead of an int dp matrix, I use string dp matrix directly. Therefore the reconstruction is a little bit easier at the expense of more memory use (but same complexity if only n is counted). The string dp matrix idea is from the jave solution of @uwi. \n\n```\n    string shortestSuperstring(vector<string>& A) {\n        int n = A.size();\n        // dp[mask][i] : min superstring made by strings in mask,\n        // and the last one is A[i]\n        vector<vector<string>> dp(1<<n,vector<string>(n));\n        vector<vector<int>> overlap(n,vector<int>(n,0));\n        \n        // 1. calculate overlap for A[i]+A[j].substr(?)\n        for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(i!=j){\n            for(int k = min(A[i].size(), A[j].size()); k>0; --k)\n                if(A[i].substr(A[i].size()-k)==A[j].substr(0,k)){\n                    overlap[i][j] = k; \n                    break;\n                }\n        }\n        // 2. set inital val for dp\n        for(int i=0; i<n; ++i) dp[1<<i][i] += A[i];\n        // 3. fill the dp\n        for(int mask=1; mask<(1<<n); ++mask){\n            for(int j=0; j<n; ++j) if((mask&(1<<j))>0){\n                for(int i=0; i<n; ++i) if(i!=j && (mask&(1<<i))>0){\n                    string tmp = dp[mask^(1<<j)][i]+A[j].substr(overlap[i][j]);\n                    if(dp[mask][j].empty() || tmp.size()<dp[mask][j].size())\n                        dp[mask][j] = tmp;\n                }\n            }\n        }\n        // 4. get the result\n        int last = (1<<n)-1;\n        string res = dp[last][0];\n        for(int i=1; i<n; ++i) if(dp[last][i].size()<res.size()){\n            res = dp[last][i];\n        }\n        return res;\n    }\n```
[]