[C++] DP
Approach 1: DP [1]\n\nclass Solution {\npublic: \n    string shortestSuperstring(vector<string>& A) {\n        const int n = A.size();\n        vector<vector<in
Approach 1: DP [1]\n```\nclass Solution {\npublic: \n    string shortestSuperstring(vector<string>& A) {\n        const int n = A.size();\n        vector<vector<int> > g(n, vector<int>(n));\n        for(int i = 0; i < n; i++)\n            for(int j = 0; j < n; j++){\n                g[i][j] = A[j].length();\n                for(int k = 1; k <= min(A[i].length(), A[j].length()); k++){\n                    if(A[i].substr(A[i].length()- k) == A[j].substr(0, k)){\n                        g[i][j] = A[j].length() - k;\n                    }\n                }\n            }\n        \n        vector<vector<int> > dp(1<<n, vector<int>(n, INT_MAX/2));\n        vector<vector<int> > parent(1<<n, vector<int>(n, -1));\n        for(int i = 0; i < n; i++){ dp[1<<i][i] = A[i].length();}        \n        \n        for(int s = 1; s < (1<<n); s++){\n            for(int j = 0; j < n; j++){\n                if(!s&(1<<j)) continue;\n                //if(!(s&(1<<j))) continue;\n                int ps = s & ~(1<<j);\n                for(int i = 0; i < n; i++){\n                    if(dp[s][j] > dp[ps][i] + g[i][j]){\n                        dp[s][j] = dp[ps][i] + g[i][j];\n                        parent[s][j] = i;\n                    }\n                }\n            }\n        }\n        \n        string res;\n        auto it = min_element(begin(dp.back()), end(dp.back()));\n        int j = it - begin(dp.back()); // cur\n        int s = (1 << n) - 1;\n        while(s){\n            int i = parent[s][j]; // pre\n            if(i < 0) res = A[j] + res;\n            else res = A[j].substr(A[j].length() - g[i][j]) + res;            \n            s &= ~(1<<j);\n            j = i;\n        }\n        return res;        \n    }\n};\n```\nReference:\n[1] https://zxi.mytechroad.com/blog/searching/leetcode-943-find-the-shortest-superstring/
['Dynamic Programming', 'C']