[LeetCode]Word Subsets

这道题naive的做法就是对于A中的每个string a, 我们遍历B里的每一个string看其是否为a的subset。假设A有n个string，平均长度为p; B有m个string，平均长度为q，那么总的时间复杂度为O(n * p * m * q)，比较高，会TLE。优化的思路不难，显然我们对于每个a都要变B种所有string代价太高了，如果我们对B中的string做预处理，把其归纳成一个pattern，然后用每个a去match这个pattern就会容易的多。根据B来建立整个pattern，我们用hashmap来记录对应的每一个字符在A中至少需要的数量，然后对于每一个a来判断这是否合法。时间复杂度O(n * p + m * q)，因为总共就26个字符，判定是否合法只需要常数时间。代码如下：

	class Solution {
	public:
	vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
	vector<string> res;
	auto pattern = getPattern(B);
	for(const auto& a : A)
	{
	unordered_map<char, int> cnts;
	bool isUniversal = true;
	for(auto& c : a)++cnts[c];
	for(auto& p : pattern)
	{
	char key = p.first;
	int cnt = p.second;
	if(cnts.find(key) == cnts.end() || cnts[key] < cnt)
	{
	isUniversal = false;
	break;
	}
	}
	if(isUniversal)res.push_back(a);
	}
	return res;
	}
	private:
	unordered_map<char, int> getPattern(vector<string>& B)
	{
	unordered_map<char, int> res;
	for(auto& b : B)
	{
	unordered_map<char, int> curr;
	for(auto& c : b)++curr[c];
	for(auto& p : curr)
	{
	char key = p.first;
	int cnt = p.second;
	if(res.find(key) == res.end() || res[key] < cnt)
	res[key] = cnt;
	}
	}
	return res;
	}
	};

view raw Word Subsets.cpp hosted with ❤ by GitHub