Leetcode-Find Common Characters

1. 本题链接
2. 更多

1002. Find Common Characters

描述：Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer. You may return the answer in any order. Example 1: Input: [“bella”,”label”,”roller”] Output: [“e”,”l”,”l”] Example 2: Input: [“cool”,”lock”,”cook”] Output: [“c”,”o”] Note: 1 <= A.length <= 100 1 <= A[i].length <= 100

1. my solution

   class Solution {
   public:
    vector<string> commonChars(vector<string>& A) {
        char cha;
        string str=" ";
        int frequency;
        vector<string> ans;
        //这样定义vec_m，时空开销是184 ms，90.7 MB
        map<char,int> m;
        vector<map<char,int>> vec_m;
           
        for(auto word: A)
        {
            for(auto c: word)
                m[c]++;
            vec_m.push_back(m);
            m.clear();
        }
                   
        for(cha='a';cha<='z';cha++)
        {
            frequency=100;
            for(auto map: vec_m)
            {           
                frequency=min(frequency,map[cha]); 
            }
            while(frequency)
            {
                str[0] = cha;
                ans.push_back(str);
                frequency--;
            }
        }
                   
        return ans;
    }
   };
   

2. my modified version

   class Solution {
   public:
    vector<string> commonChars(vector<string>& A) {
        char cha;
        //string str=" ";
        int frequency,i;
        vector<string> ans; 
        //vec_m记录A中每个单词中，每个字母的频数。
        //我们可以看到，使用二维数组替换掉vector<map<char,int>>，时空开销是8 ms，9.4 MB            
        int vec_m[A.size()][26]={0}; 
              
        for(i=0;i<A.size();i++)
        {
            for(auto c: A[i])
                vec_m[i][c-'a']++;
        }
        for(cha='a';cha<='z';cha++)
        {
            frequency=100;
            for(i=0;i<A.size();i++)
            {           
                frequency=min(frequency,vec_m[i][cha-'a']); 
            }
            while(frequency)
            {
                //str[0] = cha;
                ans.push_back(string(1,cha));
                frequency--;
            }
        }
                   
        return ans;
    }
   };
   

3. 使用2个vector，来自Discuss

     vector<int> cnt(26, 100);//1 <= A[i].length <= 100
     vector<string> res;
     for (auto s : A) {
    vector<int> cnt1(26, 0);
    for (auto c : s) ++cnt1[c - 'a'];
    for (auto i = 0; i < 26; ++i) cnt[i] = min(cnt[i], cnt1[i]);
     }
     for (auto i = 0; i < 26; ++i)
    for (auto j = 0; j < cnt[i]; ++j) res.push_back(string(1, i + 'a'));
     return res;
   

• Previous
  GAN基本原理
• Next
  Leetcode-Relative Sort Array