解题思想:字符串中字符出现频率取交集,最终将交集中的字符都计入结果
创建一个最小频率数组minfreq,和临时频率数组tmp;
遍历字符串数组,每次遍历前将临时tmp置0,然后计算每个字符频率,遍历一个字符串后就将tmp和minfreq进行取交集,即更新minfreq值
最终构造结果集,对26个字母的公共最小出现频率计入结果
class Solution { public: vector<string> commonChars(vector<string>& A) { // 构造两个数组,存放字符出现频率和最小出现频率 vector<int> minfreq(26,INT_MAX); vector<int> freq(26);//遍历每个字符串时来临时存放出现频率 // 遍历A,且每次遍历都要freq置全0 // 统计每个字符串中每个字符出现频率 for(const string &word:A){ fill(freq.begin(),freq.end(),0);//清空 for(char c:word){//遍历字符 freq[c-'a']++;//统计 } for(int i=0;i<26;i++){//将每个字符串的freq和minfreq取交集,更新minfreq值 minfreq[i]=min(minfreq[i],freq[i]); } } // 构造结果集 vector<string> res; // 对26个字符进行统计,有的字符没有在全部字符串中出现,或没出现过,则minfreq为0则不统计 // 其他出现多次的统统计入结果 for(int i=0;i<26;i++){ for(int j=0;j<minfreq[i];j++){ res.emplace_back(1,i+'a');//出现minfreq[i]次,便显示多少次,即插入多少次 } } return res; } };