[C++] Greedy merge 2 strings a time. Pick the 'best' pair according to heuristics.
\nclass Solution {\n    static bool cmp(vector<int>& a, vector<int>& b) {\n        int ascore = a[0]-a[3]-a[4];\n        int bscore = b[0]-b[3]-b[4];\n        i
```\nclass Solution {\n    static bool cmp(vector<int>& a, vector<int>& b) {\n        int ascore = a[0]-a[3]-a[4];\n        int bscore = b[0]-b[3]-b[4];\n        if (ascore>bscore) return true;\n        if (ascore<bscore) return false;\n        return (a[0]>b[0]);\n    }\n    void printvv(const vector<vector<int>>& vv) {\n        for (vector<int> row : vv) {\n            for (int elem : row)\n                cout << elem << ", ";\n            cout << endl;\n        }\n    }\n    void printvs(const vector<string>& vs) {\n        for (string s : vs)\n            cout << s << ", ";\n        cout << endl;\n    }\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        while (words.size()>1) {\n            int n = words.size();\n            vector<vector<int>> vv;\n            for (int i=0; i<n; i++) {\n                int wordi_len = words[i].length();\n                for (int j=0; j<n; j++) {\n                    if (i==j) continue;\n                    int min_len = min(wordi_len, (int)words[j].length());\n                    int common_len = 0;\n                    for (int k=1; k<=min_len; k++) {\n                        string t = words[i].substr(wordi_len-k);\n                        if (0 == words[j].find(t))\n                            common_len = max(common_len, k);\n                    }\n                    vector<int> row{common_len, i, j, 0, 0};\n                    vv.push_back(row);\n                }\n            }\n            //printvv(vv);\n            int m = vv.size();\n            for (int i=0; i<m; i++) {\n                int maxFrom=0;\n                for (int j=0; j<m; j++) {\n                    if (i==j) continue;\n                    if (vv[j][1]!=vv[i][1])\n                        continue;\n                    maxFrom = max(maxFrom, vv[j][0]);\n                }\n                vv[i][3] = maxFrom;\n            }\n            for (int i=0; i<m; i++) {\n                int maxTo=0;\n                for (int j=0; j<m; j++) {\n                    if (i==j) continue;\n                    if (vv[j][2]!=vv[i][2])\n                        continue;\n                    maxTo = max(maxTo, vv[j][0]);\n                }\n                vv[i][4] = maxTo;\n            }\n            sort(vv.begin(), vv.end(), cmp);\n            //printvv(vv);\n            int i = vv[0][1];\n            int j = vv[0][2];\n            string combined_word = words[i] + words[j].substr(vv[0][0]);\n            if (i>j) {\n                words.erase(words.begin()+i);\n                words.erase(words.begin()+j);\n            } else {\n                words.erase(words.begin()+j);\n                words.erase(words.begin()+i);\n            }\n            words.push_back(combined_word);\n            //printvs(words);\n        }\n        return words[0];\n    }\n};\n```
[]