[c++] deep-first search with memorization
\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        size_t n = words.size();\n        vector<vector<int>> overlap(n, v
```\nclass Solution {\npublic:\n    string shortestSuperstring(vector<string>& words) {\n        size_t n = words.size();\n        vector<vector<int>> overlap(n, vector<int>(n));\n        for (size_t i = 0; i < n; ++i) \n            for (size_t j = 0; j < n; ++j)\n                update(i, j, words, overlap);\n        vector<vector<int>> dp(n, vector<int>(1 << n, -1));\n        vector<vector<int>> next(n, vector<int>(1 << n, -1));\n        int max_length = -1;\n        int curr = -1;\n        vector<int> max_path;\n        for (size_t i = 0; i < n; ++i) {\n            dfs(i, overlap, 0, dp, next);\n            if (dp[i][0] > max_length) {\n                max_length = dp[i][0];\n                curr = i;\n            }\n        }\n        vector<size_t> path;\n        path.push_back(curr);\n        int bitmask = 0;\n        while (next[curr][bitmask] >= 0) {\n            path.push_back(next[curr][bitmask]);\n            bitmask ^= (1 << curr);\n            curr = path.back();\n        }\n        string ans = words[path[0]];\n        for (size_t i = 1; i < n; ++i) \n            ans += words[path[i]].substr(overlap[path[i-1]][path[i]]);\n        return ans;\n    }\n    \n\t//build the overlap graph\n    void update(size_t i, size_t j, vector<string>& words, vector<vector<int>>& overlap) {\n        if (i == j) \n            return;\n        size_t n1 = words[i].size();\n        size_t n2 = words[j].size();\n        size_t n = min(n1, n2);\n        int count = 0;\n        for (size_t k = n; k > 0; --k) {\n            if (words[i].substr(n1 - k) == words[j].substr(0, k)) {\n                overlap[i][j] = k;\n                return;\n            }\n        }\n    }\n    \n\t\n\t//deep-first search with memerization\n\t//"i" is the current node; "bitmask" saves previously visited nodes; "dp" saves the longest lengh with the remaining nodes\n\t//"next" saves the next node we should go in the current situation, used to recover the path in the end\n    void dfs(size_t i, vector<vector<int>>& overlap, int bitmask, vector<vector<int>>& dp, vector<vector<int>>& next) {\n        if (dp[i][bitmask] >= 0)\n            return;\n        size_t n = overlap.size();\n        bitmask ^= (1 << i);\n        int remain_length = -1;\n        int next_node = -1;\n        for (size_t j = 0; j < n; ++j) {\n            if (!((1 << j) & bitmask)) {\n                dfs(j, overlap, bitmask, dp, next);\n                if (overlap[i][j] + dp[j][bitmask] > remain_length) {\n                    remain_length = overlap[i][j] + dp[j][bitmask];\n                    next_node = j;\n                }\n            }\n        }\n        bitmask ^= (1 << i);\n        dp[i][bitmask] = max(0, remain_length);\n        next[i][bitmask] = next_node;\n        return;\n    }\n};\n```
[]