一、问题描述
We are given two arrays A and B of words. Each word is a string of lowercase letters.
Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".
Now say a word a from A is universal if for every b in B, b is a subset of a.
Return a list of all universal words in A. You can return the words in any order.
Example 1:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]
Example 2:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]
Example 3:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]
Example 4:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]
Example 5:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]
Note:
1 <= A.length, B.length <= 100001 <= A[i].length, B[i].length <= 10A[i] and B[i] consist only of lowercase letters.A[i] are unique: there isn‘t i != j with A[i] == A[j].#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
bool isUniversal(string& word, std::map<char, int> chr_map)
{
for(auto c:word){
if(chr_map.find(c) != chr_map.end())
chr_map[c] -= 1;
}
std::map<char, int>::iterator it = chr_map.begin();
while (it != chr_map.end()) {
if((it->second) > 0)
return false;
it++;
}
return true;
}
class Solution {
public:
vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
std::map<char, int> chr_map;
std::vector<string> result;
for(auto word:B){
std::map<char, int> chr_temp_map;
for(auto c:word){
chr_temp_map[c] += 1;
}
for (auto& kv : chr_temp_map) {
chr_map[kv.first] = std::max(kv.second, chr_map[kv.first]);
}
}
for(auto w: A){
if(isUniversal(w, chr_map))
{
result.push_back(w);
}
}
return result;
}
};
void test()
{
std::map<char, int> chr_map;
std::vector<string> result{"abc","bcd","cde"};
for(auto word:result){
for(auto c:word){
chr_map[c] += 1;
cout<<chr_map[c]<<endl;
}
}
std::map<char, int> chr_map_copy(chr_map);
}
int main(int argc, const char * argv[]) {
// insert code here...
// test();
Solution s;
vector<string> A{"amazon","apple","facebook","google","leetcode"};
vector<string> B{"lo","eo"};
s.wordSubsets(A, B);
return 0;
}
三、总结
这道题目没有特殊，主要是理解题意。
用到std::<string> map，for 遍历 c++11的语法
编译需要添加 -std=c++11 参数
Leetcode-916. Word Subsets-(Medium)
原文：https://www.cnblogs.com/doudouyoutang/p/10190507.html