String Matching || Bitmask || DP || Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nBitMask and dp\n\n# Complexity\n- Time complexity:\nO((1<<12)(13))\n\n- S
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nBitMask and dp\n\n# Complexity\n- Time complexity:\nO((1<<12)*(13))\n\n- Space complexity:\nO((1<<12)*(13))\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int overlap[13][13];\n    int Max_overlap(string &a,string &b){\n        int ans=0;\n        for(int i=0;i<a.size();i++){\n           int j=0;\n           for(j=0;j<b.size() && i+j<a.size();j++){\n               if(a[i+j]!=b[j])break;\n           }\n           if(i+j==a.size())ans=max(ans,j);      \n        }\n        return ans;\n    }\n    int dp[1<<12][13];\n   \n    string shortestSuperstring(vector<string>& words) {\n        int n=words.size();\n        memset(overlap,0,sizeof(overlap));\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                overlap[i][j]=Max_overlap(words[i],words[j]);\n            }\n        }\n        memset(dp,-1,sizeof(dp));\n        int min_length=find(12,n,0,words);\n        string ans="";\n        shortest_string(12,n,0,words,ans,min_length);\n        return ans;\n    }\n    void shortest_string(int pre,int &n,int mask,vector<string>&words,string &ans,int &l){\n        \n        for(int i=0;i<n;i++){\n            if(mask&(1<<i))continue;\n            int p=words[i].size()-overlap[pre][i];\n            if(dp[mask^(1<<i)][i]==l-p){\n                for(int x=overlap[pre][i];x<words[i].size();x++){\n                    ans.push_back(words[i][x]);\n                }\n                l-=p;\n                shortest_string(i,n,mask^(1<<i),words,ans,l);\n                break;\n            }\n        }\n\n    }\n    int find(int pre,int &n,int mask,vector<string>&words){\n        if(mask==(1<<n)-1)return dp[mask][pre]=0;\n        if(dp[mask][pre]!=-1)return dp[mask][pre];\n        int ans=INT_MAX;\n        for(int i=0;i<n;i++){\n            if(mask&(1<<i))continue;\n            int x=words[i].size()-overlap[pre][i];\n            ans=min(ans,x+find(i,n,mask^(1<<i),words));\n        }\n        return dp[mask][pre]=ans;\n    }\n};\n```
['C++']