943. Find the Shortest Superstring

https://leetcode.com/problems/find-the-shortest-superstring/description/

给定一串字符串A，找出现了A中所有字符串的最短字符串。最短肯定是尽量让两个词有overlap，而找出访问了所有结点的最短路径，即汉密尔顿问题，是NP-hard，目前只可能有指数级别的解。纯暴力DFS是找出所有可能的遍历路径，是阶乘级别的。但实际上这道题用DP可以降到指数级别，因为它满足DP的无后效性（马尔可夫）: 只用知道哪些已经遍历过了，且最后结点是i, 而不用实时追踪具体怎么走到的i。 由于题目要求返回字符串，不止是长度，因此还需要记录最优是怎么走的。

参考自花花。

/*
 * @lc app=leetcode id=943 lang=cpp
 *
 * [943] Find the Shortest Superstring
 *
 * https://leetcode.com/problems/find-the-shortest-superstring/description/
 *
 * algorithms
 * Hard (38.95%)
 * Likes:    199
 * Dislikes: 57
 * Total Accepted:    6K
 * Total Submissions: 15.3K
 * Testcase Example:  '["alex","loves","leetcode"]'
 *
 * Given an array A of strings, find any smallest string that contains each
 * string in A as a substring.
 * 
 * We may assume that no string in A is substring of another string in A.
 * 
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: ["alex","loves","leetcode"]
 * Output: "alexlovesleetcode"
 * Explanation: All permutations of "alex","loves","leetcode" would also be
 * accepted.
 * 
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
 * Output: "gctaagttcatgcatc"
 * 
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * 1 <= A.length <= 12
 * 1 <= A[i].length <= 20
 * 
 * 
 * 
 * 
 * 
 */
class Solution {
public:
    string shortestSuperstring(vector<string>& A) {
        const auto dist = [](const string &a, const string &b) {
            int d = b.length();
            for (int k = 1; k <= min(a.length(), b.length()); ++k) {
                if (a.substr(a.size() - k) == b.substr(0, k)) d = b.length() - k;
            }
            return d;
        };
        const int N = A.size();
        vector<vector<int>> g(N, vector<int>(N));
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                g[i][j] = dist(A[i], A[j]);
                g[j][i] = dist(A[j], A[i]);
            }
        }
        // <哪些被访问过的状态，末尾>
        vector<vector<int>> dp(1 << N, vector<int>(N, INT_MAX / 2));
        vector<vector<int>> parent(1 << N, vector<int>(N, -1));
        for (int i = 0; i < N; ++i) dp[1 << i][i] = A[i].length();
        for (int s = 1; s < (1 << N); ++s) {
            for (int i = 0; i < N; ++i) {
                // i没有访问过，跳过
                if (!(s & (1 << i))) continue;
                // i 位置空，即上一状态
                int prev = s - (1 << i);
                for (int j = 0; j < N; ++j) {
                   if (dp[prev][j] + g[j][i] < dp[s][i]) {
                       dp[s][i] = dp[prev][j] + g[j][i];
                       parent[s][i] = j;
                   } 
                }
            }
        }
        auto it = min_element(begin(dp.back()), end(dp.back()));
        int cur = it - begin(dp.back());
        int s = (1 << N) - 1;
        string res;
        while (s) {
            int prev = parent[s][cur];
            if (prev < 0) res = A[cur] + res;
            else res = A[cur].substr(A[cur].length() - g[prev][cur]) + res;
            s &= ~(1 << cur);
            cur = prev;
        }
        return res;
    }
};