DP Bitmask (Iterative/Bottom Up) (TSP)
Intuition\nThis problem is analogous to the travelling salesman problem, as we need to start from any one string and visit all other strings, such that the tota
# Intuition\nThis problem is analogous to the travelling salesman problem, as we need to start from any one string and visit all other strings, such that the total length is minimum.\n\n# Approach\nWe can create a state as `(mask, curr_node)`. The `mask` represents the set of visited nodes, and we are currently at `curr_node`. Now, for the cost, of moving from one string to another, we can choose the cost to be the total length of string after combining. For instance, for moving from `ttca` to `catg`, the cost will be 6 as the final string will be `ttcatg`, of length 6. \n\nHowever, this will yield incorrect results as the cost will also be dependent on the absolute length of a string, rather than only the overlap. So, we choose the maximize the overlap, rather that minimizing the cost. Overlap in the case of `ttca` and `catg` is 2.\n\n- While iterating, we also need to store the parent of a state, so that we can trace the path later on. We only need to store the parent node, and not the parent mask in `parent[mask][curr_node]`, as we can get the parent mask by setting off the `curr_node` from the `mask`.\n\n- Strings which will have overlap 0 with every string, will not be present in the the path. So, we need to add all these strings at the end.\n\n# Complexity\nSame as that of the Held-Karp DP, used to solve TSP\n- Time complexity: $O(n^2*2^n)$\n- Space complexity: $O(n*2^n)$\n\n# Code\n```cpp\nclass Solution {\n    int computeOverlap(string s, string t) {\n        int n = s.size();\n        int m = t.size();\n        int idx = n;\n\n        for (int i = n - 1;i>=0;i--) {\n            if (s.substr(i, (n - i)) == t.substr(0, n - i)) {\n                idx = i;\n            }\n        }\n        return n - idx;\n    }\n\n    // returns the uncommon part in the string s. For s == `ttca` and t == `catg`\n    // the function returns `tt`\n    string computeUncommonPart(const string &s,const string &t) {\n        int n = s.size();\n        int m = t.size();\n        int idx = n;\n\n        for (int i = n - 1;i>=0;i--) {\n            if (s.substr(i, (n - i)) == t.substr(0, n - i)) {\n                idx = i;\n            }\n        }\n        if (idx == n) {\n            return s;\n        }\n        return s.substr(0, idx);\n    }\n\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        int n = words.size();\n        vector<vector<int>> overlap(n, vector<int> (n));\n        vector<vector<int>> parent(1 << n, vector<int> (n, -1));\n        vector<vector<int>> dp(1 << n, vector<int> (n));\n\n        for (int i = 0;i<n;i++) {\n            for (int j = 0;j<n;j++) {\n                if (i != j) {\n                    overlap[i][j] = computeOverlap(words[i], words[j]);\n                }\n            }\n        }\n\n        for (int mask = 0;mask < (1<<n); mask++) {\n            for (int i = 0;i<n;i++) {\n                if ((mask)&(1<<i)) {\n                    for (int j = 0;j<n;j++) {\n                        if (((mask)&(1<<j)) == 0) {\n                            if (dp[mask | 1<<j][j] < dp[mask][i] + overlap[i][j]) {\n                                dp[mask | 1<<j][j] = dp[mask][i] + overlap[i][j];\n                                parent[mask | 1<<j][j] = i;\n                            }\n                        }\n                    }\n                } \n            }\n        }\n\n        // find the node with maximum overlap.\n        int mx = 0;\n        int dest = -1;\n        for (int i = 0;i<n;i++) {\n            if (dp[(1<<n) - 1][i] > mx) {\n                mx = dp[(1<<n) - 1][i];\n                dest = i;\n            }\n        }\n\n        // trace back the path\n        vector<bool> visited(n);\n        vector<string> res;\n        int mask = (1<<n) - 1;\n        int src = dest;\n        while (dest != -1) {\n            res.push_back(words[dest]);\n            visited[dest] = true;\n            int prev = parent[mask][dest];\n            mask ^= (1<<dest);\n            dest = prev;\n        }\n\n        reverse(res.begin(), res.end());\n        for (int i = 0;i<n;i++) {\n            if(!visited[i]) {\n                res.push_back(words[i]);\n                visited[i] = true;\n            }\n        }\n        \n        string ans = "";\n        for (int i = 0;i<n-1;i++) {\n            string uncommonPart = computeUncommonPart(res[i], res[i+1]);\n            ans += uncommonPart;\n        }\n        ans += res[n-1];\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']