[LeetCode]Stickers to Spell Word

这道题乍看之下和背包问题比较像，都是用物品去填满背包。但是区别也是很大的，这道题实际上是用每个sticker的子集去组成target string，并且这里target被填满的状态也不是简单的一个背包体积。但是这能给我们一个很好的思路，假设我们用dp[state][j]来表示处在state状态下用前j个sticker来组成当前状态state的最小用量，那么我们需要定义state，其实很明显state应该是target string的子集。不像背包问题，对于当前物品其体积为vi，我们只需要去找对应背包体积C - vi的状态然后构造递推公式。这道题，对于一个target string 'aabcdef'，和第j个sticker 'bad'，很明显bad可以覆盖target中{a, b, d}，那么余下的待覆盖的部分就是acef，也就是说我们要寻找对于的acef可以被前j - 1个sticker覆盖的方法从而递推到aabcdef被前j个sticker覆盖的方法。那么我们的递推公式就呼之欲出了，对于target string的子集 state，对于前k个sticker，假设第k个sticker其覆盖state的子集为 sk，那么dp[state][k] = min(dp[state][k - 1]], dp[state - sk][k] + 1)，state - sk代表state除去sk剩下的字符。这个递推公式其实和完全背包问题就非常像了，如果想了解这公式是怎么来的可以参考上面的链接。那么剩下的问题就是如何表示当前string的状态state了，我们在前面说过，state就是targe string的某个子集，我们用bitmap进行状态压缩即可，再加上我们的input target string最长只有15个字符，这个暗示不能再明显了。这样我们用一个整数就可以表示当前string的状态。
具体的思路和背包问题很相似，我们每一次算出当前sticker覆盖对应state的子集，然后按照我们上面给出的递归公式计算即可。注意这里我们不开二维数组，因为子集的数量是指数级的，我们转换成一维的dp公式，我们用dp[state]表示当前state子集状态下的string用所有种类sticker覆盖的最小用量，sk代表第k个sticker覆盖state的子集。那么递推公式为dp[state] = min(dp[state - s1], dp[state - s2], ... , dp[state - sm]) + 1, 这个公式和上面的二维形式其实是一样的。
实现过程中有几个具体的细节：

• 对于当前sticker的每个字符，如果其覆盖了state当中的某个位置，显然其不应该继续搜索尝试覆盖另一个位置，所以我们一但找到一个覆盖就break
• 对于state当中的每个字符，如果其已经被覆盖，那么我们应该跳过去尝试覆盖下一位，这样避免了如果sticker和state当中有多个相同的字符的时候，sticker中的相同字符都尝试匹配state当中的同一位

时间复杂度分析，假设target string长度为n，我们有m个sticker，每个sticker平均长度为len。我们有2^n个状态，m个sticker每个状态都要遍历，每次遍历len的时间去找state的子集覆盖，那么总的时间复杂度为O(2 ^ n * len * m)，代码如下：

	class Solution {
	public:
	int minStickers(vector<string>& stickers, string target) {
	int n = target.size(), len = stickers.size();
	//dp represents minimum sticker required for current state
	//state is a binary number where each bit represents if corresponding char appears
	vector<int> dp(1 << n, n + 1);
	dp[0] = 0;
	for(int i = 1; i < 1 << n; ++i)
	{
	for(auto sticker : stickers)
	{
	int state = 0;
	for(int j = 0; j < sticker.size(); ++j)
	{
	for(int k = 0; k < n; ++k)
	{
	//if we have two same chars, two 'a's
	//if the first 'a' is matched, we don't
	//want the second 'a' to match the same
	//position in i again
	if((state >> k & 1) == 1)continue;
	if(i >> k & 1 && sticker[j] == target[k])
	{
	//if current char c in sticker is matched
	//it shouldn't match another char in i again,
	//we just break
	state |= 1 << k;
	break;
	}
	}
	}
	dp[i] = min(dp[i], dp[i - state] + 1);
	}
	}
	return dp[(1 << n) - 1] == n + 1? -1: dp[(1 << n) - 1];
	}
	};

view raw Stickers to Spell Word_1.cpp hosted with ❤ by GitHub

这个版本的运行时间是1000ms左右，而leetcode solution类似的解法相应的时间只需要250ms左右。其思路是一样的，只不过我们是每次在state状态的时候遍历所有以前的能推导过来的状态，然后根据这些计算当前状态。但是solution的解法是相反的方向，其是每次到state的时候计算所有state能推导出去的状态，这样我们每次到达state的时候，就能知道当前state需要的最小用量是多少了。这样的好处在于，我们可以避免计算很多无用的状态，如果dp[state]为-1，那么我们知道当前state从起始状态是没有办法通过我们拥有的stickers达到的，那么我们自然不需要去管他，直接跳过即可。但是在我们实现的版本中，我们没有办法辨别当前状态是否可以达到的，所以这可以给我们省下一些时间，代码如下：

	class Solution {
	public:
	int minStickers(vector<string>& stickers, string target) {
	int n = target.size(), len = stickers.size();
	//dp represents minimum sticker required for current state
	//state is a binary number where each bit represents if corresponding char appears
	vector<int> dp(1 << n, -1);
	dp[0] = 0;
	for(int i = 0; i < 1 << n; ++i)
	{
	if(dp[i] == -1)continue;
	for(auto sticker : stickers)
	{
	int state = i;
	for(int j = 0; j < sticker.size(); ++j)
	{
	for(int k = 0; k < n; ++k)
	{
	//if we have two same chars, two 'a's
	//if the first 'a' is matched, we don't
	//want the second 'a' to match the same
	//position in i again
	if((state >> k & 1) == 1)continue;
	if(sticker[j] == target[k])
	{
	//if current char c in sticker is matched
	//it shouldn't match another char in i again,
	//we just break
	state |= 1 << k;
	break;
	}
	}
	}
	if(dp[state] == -1 || dp[i] + 1 < dp[state])
	dp[state] = dp[i] + 1;
	}
	}
	return dp[(1 << n) - 1];
	}
	};

view raw Stickers to Spell Word_2.cpp hosted with ❤ by GitHub