Esay C++ Sol 🔥🔥
Code\n\nclass Solution {\npublic:\n    \n    string addFront(string a,string b)\n    {\n        int n1 = a.length();\n        int n2 = b.length();\n        stri
# Code\n```\nclass Solution {\npublic:\n    \n    string addFront(string a,string b)\n    {\n        int n1 = a.length();\n        int n2 = b.length();\n        string ans = "";\n        for(int i=b.length()-1;i>=0;i--)\n        {\n             int len = 0;\n            \n            int i1 = i;\n            int i2 = 0;\n            while(i1<b.length() && i2<a.length())\n            {\n                if(b[i1]==a[i2])\n                {\n                    i1++;\n                    i2++;\n                }\n                else\n                    break;\n            }\n            if(i2==a.length()) return b;\n            if(i1==b.length())\n            {\n                string cur = b;\n                for(int j=i2;j<a.length();j++)\n                    cur += a[j];\n                ans = cur;\n            }\n        }\n        if(ans.size()==0)\n            ans = b + a;\n        return ans;\n        \n    }\n    int solve(int v,int vis,vector<vector<int>> adj[],vector<vector<int>>& dp,int& n,vector<string>& words,vector<vector<int>>& path)\n    {\n        \n        vis |= (1<<v);\n        if(vis == pow(2,n)-1) return 0;\n        if(dp[v][vis]!=-1) return dp[v][vis];\n        \n        int ans = 1e9;\n        for(auto child : adj[v])\n        {\n            if(vis & (1<<child[0])) continue;\n            int val = solve(child[0],vis,adj,dp,n,words,path) + child[1];\n            if(val<ans)\n            {\n                ans = val;\n                path[v][vis] = child[0];\n            }\n        }\n        return dp[v][vis] = ans;\n    }\n    void fill(vector<vector<int>>& dp)\n    {\n        for(int i=0;i<dp.size();i++)\n        for(int j=0;j<dp[0].size();j++)\n        dp[i][j] = -1;\n    }\n    string getPath(int v,vector<vector<int>>& path,set<int>& vis,vector<string>& words)\n    {\n        \n        string pp = "";\n        int cur = v;\n        int mask = 1<<v;\n        while(path[cur][mask]!=-1)\n        {\n            \n            pp = addFront(words[cur],pp);\n            vis.erase(vis.find(cur));\n            int next = path[cur][mask];\n            mask  = mask | ((1<<next));\n            cur = next;\n        }\n        if(vis.size()){\n        int left = *(vis.begin());\n        pp = addFront(words[left],pp);\n        }\n        return pp;\n    }\n    string shortestSuperstring(vector<string>& words) {\n        int n = words.size();\n        // cout<<n<<"\\n";\n        if(n==1) return words[0];\n        vector<vector<int>> adj[n];\n\n        for(int i=0;i<words.size();i++)\n        {\n            for(int j=0;j<words.size();j++)\n            {\n                if(i==j) continue;\n                string common = addFront(words[j],words[i]);\n                int cost = common.size() - words[i].size();\n                adj[i].push_back({j,cost});\n            }\n        }\n        vector<vector<int>> dp(n,vector<int> (2<<n , -1));\n        vector<vector<int>> path(n,vector<int> (2<<n, -1));\n        int ans = 1e9;\n        string pathAns;\n        for(int i=0;i<words.size();i++){\n           \n            // fill(dp);\n            // fill(path);\n            int start = words[i].size();\n            int val = solve(i,0,adj,dp,n,words,path)+start;\n            if(val<ans)\n            {\n                ans = val;\n                set<int> vis;\n                for(int k=0;k<n;k++) vis.insert(k);\n                pathAns = getPath(i,path,vis,words);\n                // reverse(order.begin(),order.end());\n                \n                ans = val;\n            }\n        }\n        return pathAns;\n\n    }\n};\n```
['C++']