C++ | DP + BFS | Cleaner than official
Intuition\n Describe your first thoughts on how to solve this problem. \nVery hard problem for mortals and probably will not be on interview but worth doing to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nVery hard problem for mortals and probably will not be on interview but worth doing to improve skills and expand DP understanding.\n\nNot immediately obviously that it\'s DP problem. We want build word paths with help of memoize (dp) of best score based on mask and last word in current path. Runtime reduction here is that multiple paths can end up at the same mask / last visited.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDon\'t be put off by bitmask, it\'s just a clean as possible way of tracking which words have been visited. This tests if you know basic bit manipulations well - which by itself is an easy problem. This problem is hard since it puts so many concepts together.\n\nThe official solution (at time of writing) uses a loop to go through the dp search space but it\'s more intuitive to do BFS. Once you have a path, you know that other paths are just adding each of the possible words left.\n\nKeep a parent array to let us back trace back.\n\nOnce DP step is done, take highest score that ends with mask of all words used (11111...111). Then use the parent vector to backtrace.\n\n# Runtime\n\n# Code\n```\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        const size_t N = words.size();\n        vector<vector<int>> overlap = vector<vector<int>>(N, vector<int>(N, 0));\n        // pre-calculate the distance (number of shared characters) between each word pair in each direction \n        for (int i = 0; i < N-1; i++)\n        {\n            for (int j = i+1; j < N; j++)\n            {\n                overlap[i][j] = Overlap(words[i], words[j]);\n                overlap[j][i] = Overlap(words[j], words[i]);\n            }\n        }\n\n        const size_t R = pow(2, N);\n        DP dp = DP(R, vector<int>(N, 0));\n        DP parent = DP(R, vector<int>(N,0));\n        vector<bool> visited = vector<bool>(R,0);\n        \n        list<int> q{};\n        for (int i = 0; i < N; i++)\n        {\n            const int mask = 1 << i;\n            q.emplace_back(1 << i);\n        }\n\n        while (!q.empty())\n        {\n            int mask = q.front(); q.pop_front();\n            for (int i = 0; i < N; i++)\n            {\n                if ((mask & (1 << i)) == 0) continue;\n                \n                int prev = mask ^ (1<<i);\n                if (prev == 0) continue;\n                for (int j = 0; j < N; j++)\n                {\n                    if ((prev & (1<<j)) == 0) continue;\n                    \n                    int score = dp[prev][j] + overlap[j][i];\n                    if (score >= dp[mask][i])\n                    {\n                        dp[mask][i] = score;\n                        parent[mask][i] = j;\n                    }\n                }\n            }\n\n            for (int i = 0; i < N; i++)\n            {\n                int next = mask | (1 << i);\n                if (!visited[next])\n                {\n                    visited[next] = true;\n                    q.emplace_back(next);\n                }\n            }\n        }\n\n        int curr = 0;\n        int max_score = *max_element(dp[R-1].begin(), dp[R-1].end()); \n        for (int i = 0; i < N; i++)\n        {\n            if (dp[R-1][i] == max_score) curr = i;\n        }\n\n        list<int> path{curr};\n        int curr_mask = R-1;\n        for(int i = 1; i < N; i++)\n        {\n            int prev = curr;\n            curr = parent[curr_mask][curr];\n            curr_mask = curr_mask & (~(1 << prev));\n            path.emplace_front(curr);\n        }\n\n        auto prev = path.begin();\n        string res = words[*prev];\n        for (auto it = ++path.begin(); it != path.end(); it++)\n        {\n            res += words[*it].substr(overlap[*prev][*it]);\n            prev = it;\n        }\n\n        return res;\n    }\nprivate:\n    using DP = vector<vector<int>>;\n\n    inline int Overlap(string front, string end)\n    {\n        int max_overlap = min(front.size(),end.size());\n        while (max_overlap > 0)\n        {\n            int j = 0;\n            bool possible = true;\n            for (int i = front.size()-max_overlap; i < front.size() && possible; i++)\n            {\n                if (front[i] != end[j]) possible = false;\n                j++;\n            }\n            if (possible) return max_overlap;\n            max_overlap--;\n        }\n        return 0;\n    }\n};\n```
['C++']