Problem: 916. Word Subsets 单词子集
对words1中的单词统计每个字符的频次，对words2统计每个单词的字符频次并且取每个单词的最大频次拿到并集，最后查找words1频次找到符合要求的单词
Code
class Solution { public: vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) { int n = words1.size(); vector<unordered_map<char, int>> tr(n); for (int i = 0; i < n; i++) { unordered_map<char, int> ump; for (int j = 0; j < words1[i].size(); j++) { ump[words1[i][j]]++; } tr[i] = ump; } vector<int> ch(26, 0); for (int k = 0; k < words2.size(); k++) { vector<int> tmp(26, 0); for(int i = 0; i < words2[k].size(); i++) { tmp[words2[k][i]-'a']++; } for(int i = 0; i < 26; i++) { ch[i] = max(tmp[i], ch[i]); } } unordered_map<char, int> umpump; for(int j = 0; j < 26; j++) { umpump[j + 'a'] = ch[j]; } bool find; vector<string> ret; for (int i = 0; i < n; i++) { find = true; for(auto&& [k, l] : umpump) { if(tr[i][k] < l) { find = false; break; } } if(find == true) { ret.push_back(words1[i]); } } return ret; } };
