(C++) 943. Find the Shortest Superstring
top-down\n\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        int n = size(words); \n        vector<vector<int>> ovlp(
**top-down**\n```\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        int n = size(words); \n        vector<vector<int>> ovlp(n, vector<int>(n, 0)); \n        \n        for (int i = 0; i < n; ++i) \n            for (int j = 0; j < n; ++j) \n                for (int k = 0; k < min(size(words[i]), size(words[j])); ++k) \n                    if (words[i].substr(size(words[i])-k) == words[j].substr(0, k))\n                        ovlp[i][j] = k; // extra length upon appending j to i \n        \n        map<pair<int, int>, pair<int, int>> memo; \n        \n        function<pair<int, int>(int, int)> fn = [&](int prev, int mask) {\n            pair key = make_pair(prev, mask); \n            if (memo.find(key) == memo.end()) {\n                if (mask == 0) return make_pair(0, 0); \n                int vv = INT_MAX, kk = -1; \n                for (int k = 0; k < n; ++k) {\n                    if (mask & 1 << k) {\n                        auto [v, tmp] = fn(k, mask ^ 1 << k); \n                        int offset = prev == -1 ? size(words[k]) : size(words[k]) - ovlp[prev][k]; \n                        if (v + offset < vv) {\n                            vv = v + offset; \n                            kk = k; \n                        }\n                    }\n                }\n                memo[key] = make_pair(vv, kk); \n            } \n            return memo[key]; \n        };\n        \n        string ans; \n        int prev = -1, mask = (1 << n) - 1; \n        while (mask) {\n            auto [tmp, k] = fn(prev, mask); \n            if (ans.size()) ans += words[k].substr(ovlp[prev][k]); \n            else ans += words[k]; \n            prev = k; \n            mask ^= 1 << k; \n        }\n        return ans; \n    }\n};\n```\n\nshorter but slower\n```\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        int n = size(words); \n        vector<vector<int>> ovlp(n, vector<int>(n, 0)); \n        \n        for (int i = 0; i < n; ++i) \n            for (int j = 0; j < n; ++j) \n                for (int k = 0; k < min(size(words[i]), size(words[j])); ++k) \n                    if (words[i].substr(size(words[i])-k) == words[j].substr(0, k))\n                        ovlp[i][j] = k;\n        \n        map<pair<int, int>, string> memo; \n        \n        function<string(int, int)> fn = [&](int prev, int mask) {\n            pair key = make_pair(prev, mask); \n            if (memo.find(key) == memo.end()) {\n                if (mask == 0) return string(); \n                string ss = string(250, \'*\'); \n                for (int k = 0; k < n; ++k) {\n                    if (mask & 1<<k) {\n                        auto s = fn(k, mask ^ 1<<k); \n                        int offset = prev == -1 ? 0 : ovlp[prev][k]; \n                        if (size(words[k]) - offset + size(s) < size(ss)) {\n                            ss = words[k].substr(offset) + s; \n                        }\n                    }\n                }\n                memo[key] = ss; \n            } \n            return memo[key]; \n        };\n        \n        return fn(-1, (1<<n) - 1);\n    }\n};\n```\n\n**bottom-up**\n```\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        int n = size(words); \n        \n        vector<vector<int>> ovlp (n, vector<int>(n)); \n        for (int i = 0; i < n; ++i) \n            for (int j = 0; j < n; ++j)\n                for (int k = 0; k < min(size(words[i]), size(words[j])); ++k)\n                    if (words[i].substr(size(words[i]) - k) == words[j].substr(0, k)) {\n                        ovlp[i][j] = k; \n                    }\n        \n        vector<vector<int>> dp(1<<n, vector<int>(n)); // min length of mask ending at bit \n        vector<vector<int>> parent(1<<n, vector<int>(n, -1)); \n        for (int mask = 0; mask < (1 << n); ++mask) {\n            for (int bit = 0; bit < n; ++bit) {\n                if (mask & 1<<bit) {\n                    int pmask = mask ^ (1<<bit); \n                    if (pmask) {\n                        for (int i = 0; i < n; ++i) {\n                            if (pmask & 1<<i) {\n                                int val = dp[pmask][i] + size(words[bit]) - ovlp[i][bit]; \n                                if (dp[mask][bit] == 0 || val < dp[mask][bit]) {\n                                    dp[mask][bit] = val; \n                                    parent[mask][bit] = i; \n                                }\n                            }\n                        }\n                    }\n                    else dp[mask][bit] = size(words[bit]); \n                }\n            }\n        }\n        \n        auto it = min_element(begin(dp.back()), end(dp.back())); \n        int mask = (1<<n) - 1, p = it - begin(dp.back()); \n        string ans; \n        while (mask) {\n            int pp = parent[mask][p]; \n            if (pp == -1) ans = words[p] + ans; \n            else ans = words[p].substr(ovlp[pp][p]) + ans; \n            mask ^= 1 << p; \n            p = pp; \n        }\n        return ans; \n    }\n}; \n```
['C']