[LeetCode]Find the Shortest Superstring

如果我们用g[i][j]表示A[i]后面接上A[j]需要添加的字符的话：

• 比如A[i] = abc, A[j] = bcd, g[i][j] = 1
• A[i] = abc, A[j] = def, g[i][j] = 3

那么建图之后，这道题就转化成了TSP问题(Travelling Salesman Problem)。简而言之，我们需要求得最短的路径，并且只通过所有节点一次。TSP问题是NP hard的，dynamic programming是一个解决的思路，但是我们仍然需要遍历所有的状态。

用dp[i][j]表示当前已经visited过的点用i的二进制为表示，并且最后一个visit的节点是j的情况下的最短路径。那么我们可以得到递推方程:

• dp[i ^ (1 << k)][k] = min(dp[i][j] + g[j][k]), where k is not visited, j can be every node visited in i

我们根据这个递推公式求得最后的结果即可。注意题目需要我们输出最后的string，所以我们需要用另一个数组parent[i][j]记录状态i j情况下最优解的前置节点。假设输入有N个string，最后的时间复杂度就为O(n^2 * 2^n)，代码如下:

	class Solution {
	public:
	string shortestSuperstring(vector<string>& A) {
	//use g[i][j] represents # of extra chars we need to add to form A[i]A[j]
	//the problem is a travelling sales man problem, nemely, find the shortest path
	//to visited every node exactly once
	int n = A.size();
	vector<vector<int>> g(n, vector<int>(n, 0));
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (i != j)
	g[i][j] = dist(A[i], A[j]);
	//dp[i][j] represents shortest path with visited node represented by i and and the
	//last node visited was j
	//dp[i ^ (1 << k)][k] = min(dp[i][j] + g[j][k]), where k is not visited, j can be every node visited in i
	vector<vector<int>> dp(1 << n, vector<int>(n, 300));
	vector<vector<int>> parent(1 << n, vector<int>(n, -1));
	//init
	for (int i = 0; i < n; ++i)
	dp[1 << i][i] = A[i].size();
	int idx = -1, res = INT_MAX;
	for (int i = 1; i < (1 << n); ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	if ((i & (1 << j)) == 0)continue;
	//get shortest path
	if (i == (1 << n) - 1 && dp[i][j] < res)
	{
	idx = j;
	res = dp[i][j];
	}
	for (int k = 0; k < n; ++k)
	{
	if (((1 << k) & i) == 0)
	{
	if (g[j][k] + dp[i][j] < dp[i | (1 << k)][k])
	{
	dp[i | (1 << k)][k] = g[j][k] + dp[i][j];
	parent[i | (1 << k)][k] = j;
	}
	}
	}
	}
	}
	//reconstruct string
	string ss;
	int state = ((1 << n) - 1), curr = idx;
	while (state)
	{
	int prev = parent[state][curr];
	ss = (prev == -1? A[curr] : A[curr].substr(A[curr].size() - g[prev][curr])) + ss;
	state -= (1 << curr);
	curr = prev;
	}
	return ss;
	}
	private:
	int dist(const string& s1, const string& s2)
	{
	int len1 = s1.size(), len2 = s2.size(), i = 1, clen = 0;
	while (i <= min(len1, len2))
	{
	if (s2.substr(0, i) == s1.substr(len1 - i))
	clen = i;
	++i;
	}
	return s2.size() - clen;;
	}
	};

view raw Find the Shortest Superstring.cpp hosted with ❤ by GitHub