Bitmasking + DP + KMP
Intuition\n1) First we need to know which one to pick before what, there 2^n  possibilities\n2) Use bit masking so that we will know how many strings are alread
# Intuition\n1) First we need to know which one to pick before what, there 2^n  possibilities\n2) Use bit masking so that we will know how many strings are already used before we pick current string.\n\n# Approach\n1) First find common substring when we combine two strings into one. which would be suffix of one and prefix of other. KMP will be easier and quicker.\n2) Then just like travelling salesman problem, start from one node and reach all other nodes with minimum cost. Whenever we reach any node, check the path how we reached that node using masking and return minimum cost path from that node.\n\n# Complexity\n- Time complexity:\nO(n^2 * 2^n)\n\n- Space complexity:\n-O(n^2 * 2^n)\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int findcpslen(string a, string b){\n        int maxi = 0;\n        string temp = b + "#" + a;\n        int j, n = temp.size();\n        vector<int> pi(n, 0);\n        for(int i = 1; i < n; i++){\n            j = pi[i-1];\n            while(j>0 && temp[i] != temp[j])\n                j = pi[j-1];\n            if(temp[i] == temp[j])\n                j++;\n            pi[i] = j;\n            maxi = max(maxi, pi[i]);\n        }\n\n        return pi[n-1];\n    }\n    string find(vector<string>& words, int idx, vector<vector<string>> &dp, vector<vector<int>> &req, int mask){\n        int n = words.size();\n\n        if(dp[idx][mask] != "")\n            return dp[idx][mask];\n        \n        dp[idx][mask] = words[idx];\n        int mini = INT_MAX;\n        for(int j = 0; j < n; j++){\n            if(idx == j || ((mask >> j) & 1))\n                continue;\n            string temp = find(words, j, dp, req, (mask | (1 << idx)));\n            if(temp.size() + n - req[idx][j] < mini){\n                mini = temp.size() + n - req[idx][j];\n                dp[idx][mask] = words[idx].substr(0, words[idx].size() - req[idx][j]) + temp;\n            }\n        }\n\n        return dp[idx][mask];\n    }\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        int n = words.size();\n        vector<vector<string>> dp(n, vector<string>(pow(2, n), ""));\n        vector<vector<int>> req(n, vector<int>(n, 0));\n        string ans = "";\n        for(int i = 0; i < n; i++){\n            ans += words[i];\n            for(int j = 0; j < n; j++){\n                if(i == j)\n                    continue;\n                req[i][j] = findcpslen(words[i], words[j]);\n            }\n        }\n\n        \n        for(int i = 0; i < n; i++){\n            string temp = find(words, i, dp, req, 0);\n            if(temp.size() < ans.size()) ans = temp;\n        }\n\n        return ans;\n    }\n};\n```
['C++']