[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个字符，判定是否合法只需要常数时间。代码如下：