C++ simple solution using dynamic programming
cpp\n#define PSI pair<string, int>\nclass Solution {\npublic:\n    int calculateOverlap(string s, string pattern){\n        for(int i=min((int)s.size(), (int)pa
```cpp\n#define PSI pair<string, int>\nclass Solution {\npublic:\n    int calculateOverlap(string s, string pattern){\n        for(int i=min((int)s.size(), (int)pattern.size()); i>0; i--){\n            if(s.substr((int)s.size()-i)==pattern.substr(0, i)){\n                return i;\n            }\n        }\n        return 0;\n    }\n    \n    inline bool isPresentInMask(int n, int mask){\n        return (((mask>>n)&1)>0);\n    }\n\n    string intToString(int n){\n        ostringstream s;\n        s<<n;\n        return s.str();\n    }\n\n    int stringToInt(string s){\n        stringstream str(s);\n        int x;\n        str >> x;\n        return x;\n    }\n\n    string getAns(string s, vector<string> words, vector<vector<int>> overlap){\n        string ans = "", temp;\n        int i=0, prev = -1, index;\n        while(i< (int)s.size()){\n            if(s[i]==\',\'){\n                index = stringToInt(temp);\n                if((int)ans.size()==0){\n                    ans = words[index];\n                }else{\n                    ans = ans + words[index].substr(overlap[prev][index]);\n                }\n                prev = index;\n                temp = "";\n            }else{\n                temp.push_back(s[i]);\n            }\n            i++;\n        }\n        index = stringToInt(temp);\n        if((int)ans.size()==0){\n            ans = words[index];\n        }else{\n            ans = ans + words[index].substr(overlap[prev][index]);\n        }\n        return ans;\n    }\n\n\n    string shortestSuperstring(vector<string>& words) {\n        int n = (int)words.size();\n        vector<vector<int>> overlap(n, vector<int>(n, 0));\n        for(int i=0; i<n; i++){\n            for(int j=0; j<n; j++){\n                if(i!=j){\n                    overlap[i][j] = calculateOverlap(words[i], words[j]);\n                }\n            }\n        }\n\n        int M = 1<<n;\n        PSI empt = {"", -1};\n        vector<vector<PSI>> dp(M, vector<PSI>(n, empt));\n        for(int i=0; i<n; i++){\n            dp[1<<i][i] = {intToString(i), 0};\n        }\n\n        for(int mask=1; mask<M; mask++){\n            for(int ennd=0; ennd<n; ennd++){\n                if(isPresentInMask(ennd, mask)){\n                    for(int i=0; i<n; i++){\n                        if(i!=ennd && isPresentInMask(i, mask)){\n                            PSI temp = {dp[mask^(1<<ennd)][i].first + "," + intToString(ennd),\n                                         dp[mask^(1<<ennd)][i].second + overlap[i][ennd]};\n\n                            if(dp[mask][ennd].second == -1 || temp.second>dp[mask][ennd].second){\n                                dp[mask][ennd] = temp;\n                            }\n                        }\n                    }\n                }\n            }\n        }\n\n        int row = M-1;\n        PSI ans = dp[row][0];\n        for(int j=1; j<n; j++){\n            if(dp[row][j].second>ans.second){\n                ans = dp[row][j];\n            }\n        }\n        return getAns(ans.first, words, overlap);\n    }\n\n};\n\n```
[]