✅ Easy Self Explanatory Code ✅ - Simple Bitmask DP + Retracing
\n# Code\n\nclass Solution {\nprivate:\n    int n, finalMask;\n    int best;\n    int dp[12][1 << 12];\n    int nextt[12][1 << 12];\n    // to find max number o
\n# Code\n```\nclass Solution {\nprivate:\n    int n, finalMask;\n    int best;\n    int dp[12][1 << 12];\n    int nextt[12][1 << 12];\n    // to find max number of common character in two string\n    int common(const string& s1 , const string& s2) {\n        int i = 1;\n        int ans = 0;\n        while(i <= s1.size() and i <= s2.size()) {\n            if(s1.substr(s1.size() - i , i) == s2.substr(0 , i))\n                ans = i;\n            i++;\n        }\n        return ans;\n    }\n    // main recursive dp function\n    int solve(vector<string>& words, int prev, int mask) {\n        // base case\n        if(mask == finalMask) {\n            return 0;\n        }\n        // memoization case\n        if(dp[prev][mask] != -1)    return dp[prev][mask];\n        // calling recursion\n        int ret = 1e9;\n        int next = -1;\n        for(int i = 0; i < n; i++) {\n            if(!(mask & (1 << i))) {\n                int comm = common(words[prev], words[i]);\n                int curr = (words[i].size() - comm) + solve(words, i, (mask | (1 << i)));\n                if(ret > curr) {\n                    ret = curr;\n                    next = i;\n                }\n            }\n        }\n        nextt[prev][mask] = next;\n        return dp[prev][mask] = ret;\n    }\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        // travelling salesman problem + retracing path using parent array\n        n = words.size();\n        finalMask = (1 << n) - 1;\n        memset(dp, -1, sizeof(dp));\n        memset(nextt, -1, sizeof(dp));\n        int mn = 1e9;\n        int begin = -1;\n        for(int i = 0; i < n; i++) {\n            int curr = words[i].size() + solve(words, i, (1 << i));\n            if(mn > curr) {\n                mn = curr;\n                begin = i;\n            }\n        }\n        // now, retracing the answer\n        string ret = "";\n        int mask = 0;\n        while(begin != -1) {\n            string prev = words[begin];\n            mask |= (1 << begin);\n            begin = nextt[begin][mask];\n            string next = begin == -1 ? "" : words[begin];\n            int comm = common(prev, next);\n            ret += prev.substr(0, prev.size() - comm);\n        }\n        return ret;\n    }\n};\n```
['String', 'Dynamic Programming', 'Memoization', 'Bitmask', 'C++']