C++ solution using DP with memoization (Beats 90% in runtime)
\nvector<vector<int> > dp,pre,par;\n\nbool startWith(string s, string t)\n{\n// returns true if string s starts with string t\n    int i;\n    for(i=0; i<s.leng
```\nvector<vector<int> > dp,pre,par;\n\nbool startWith(string s, string t)\n{\n// returns true if string s starts with string t\n    int i;\n    for(i=0; i<s.length()&&i<t.length(); i++)\n    {\n        if(s[i]==t[i])\n            continue;\n        else\n            return false;\n    }\n    if(i==t.length())\n        return true;\n    else\n        return false;\n}\n\nint calc(string A, string B)\n{\n // calculate the number of extra characters required to be appended to A\n // if A is followed by B\n // for eg. calc("abcd","cdef") = 2\n \n    int a=A.length(),b=B.length();\n    for(int i=0; i<a; i++)\n    {\n        if(a-i<=b&&startWith(B,A.substr(i)))\n        {\n            return b-(a-i); \n        }\n    }\n    return b;\n}\n\nint finalMask,n;\n\nint helper(int mask, int last)\n{\n // returns the minimum length of string required if last string appended was A[last] \n // the sets bit in mask represents the strings that were already appended to the final string\n \n    if(mask==finalMask)  // all strings are appended in final string\n        return 0;\n\n    if(dp[mask][last]!=-1) // memoization\n        return dp[mask][last];\n        \n    int mn=INT_MAX;\n    int p;\n    for(int i=0; i<n; i++)\n    {\n        if(mask&(1<<i))\n            continue;\n        int cost=pre[last][i]+helper(mask|(1<<i),i);  // extra characters need to be appended\n        if(cost<mn)\n        {\n            mn=cost;\n            p=i;\n        }\n    }\n    par[mask][last]=p;  // store parent, so that it is easy to traceback and find the final result\n    return dp[mask][last]=mn; // store result in DP table\n}\n\n\n\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& A) {\n    n=A.size();\n    pre.assign(n,vector<int>(n));  // for pre-computing calc(a,b) for all pairs of strings\n    par.assign(1<<n,vector<int>(n,-1));    \n    for(int i=0; i<n; i++)\n    {\n        for(int j=0; j<n; j++)\n        {\n            if(j==i)\n                continue;\n            pre[i][j]=calc(A[i],A[j]);\n        }\n    }\n    finalMask=(1<<n)-1;  \n    dp.assign(1<<n,vector<int>(n,-1));\n    int len=INT_MAX;  // len will contain minimum length of required string\n    int ind;\n    for(int i=0; i<n; i++)\n    {\n        int prev=len;\n        len=min(len, (int)A[i].length()+helper(1<<i,i));\n        if(len!=prev)\n        {\n            ind=i;\n        }\n    }\n\n // Now traceback to find the final answer\n    string ans=A[ind];\n    int msk=1<<ind;\n    int prev_ind=ind;\n    ind=par[msk][ind];\n    while(ind!=-1)\n    {\n        len=pre[prev_ind][ind];\n        int alen=A[ind].length();\n        ans+=A[ind].substr(alen-len,len);            \n        msk=msk^(1<<ind);\n        prev_ind=ind;\n        ind=par[msk][ind];  \n    }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C', 'C++']