Find Common Characters Solutions in C++

/// Source : https://leetcode.com/problems/find-common-characters/
/// Author : liuyubobobo
/// Time   : 2019-03-02

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/// Sorting every string
/// Using two pointers technique to get the intersection of every two strings
/// Time Complexity: O(n * ave_len_of_strings)
/// Space Complexity: O(ave_len_of_strings)
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {

        for(string& s: A) sort(s.begin(), s.end());

        string res = A[0];
        for(int i = 1; i < A.size(); i ++)
            res = intersection(res, A[i]);

        vector<string> ret;
        for(char c: res)
            ret.push_back(string(1, c));
        return ret;
    }

private:
    string intersection(const string& s1, const string& s2){

        int i1 = 0, i2 = 0;
        string res = "";
        while(i1 < s1.size() && i2 < s2.size())
            if(s1[i1] == s2[i2])
                res += s1[i1], i1 ++, i2 ++;
            else if(s1[i1] < s2[i2])
                i1 ++;
            else
                i2 ++;
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/find-common-characters/
/// Author : liuyubobobo
/// Time   : 2019-03-03

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/// Sorting and using C++ STL set_intersection :-)
/// Time Complexity: O(n * ave_len_of_strings)
/// Space Complexity: O(ave_len_of_strings)
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {

        for(string& s: A) sort(s.begin(), s.end());

        string res = A[0];
        for(int i = 1; i < A.size(); i ++){
            string cur(max(res.size(), A[i].size()), ' ');
            string::iterator iter = set_intersection(res.begin(), res.end(), A[i].begin(), A[i].end(), cur.begin());
            while(cur.size() && cur.back() == ' ') cur.pop_back();
            res = cur;
        }

        vector<string> ret;
        for(char c: res)
            ret.push_back(string(1, c));
        return ret;
    }
};


void print_vec(const vector<string>& vec){
    for(const string& s: vec) cout << s << " ";
    cout << endl;
}

int main() {

    vector<string> A1 = {"bella","label","roller"};
    print_vec(Solution().commonChars(A1));

    return 0;
}

/// Source : https://leetcode.com/problems/find-common-characters/
/// Author : liuyubobobo
/// Time   : 2019-03-03

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;


/// Using HashMap to get the intersection of every two strings
/// Time Complexity: O(n * ave_len_of_strings)
/// Space Complexity: O(26)
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {

        vector<unordered_map<char, int>> freqs(A.size());
        for(int i = 0; i < A.size(); i ++)
            for(char c: A[i])
                freqs[i][c] ++;

        unordered_map<char, int> res = freqs[0];
        for(int i = 1; i < freqs.size(); i ++)
            res = intersection(res, freqs[i]);

        vector<string> ret;
        for(const pair<char, int>& p: res)
            for(int i = 0; i < p.second; i ++)
                ret.push_back(string(1, p.first));
        return ret;
    }

private:
    unordered_map<char, int> intersection(unordered_map<char, int>& freq1,
                                          unordered_map<char, int>& freq2){

        unordered_map<char, int> res;
        for(const pair<char, int>& p: freq1)
            if(freq2.count(p.first))
                res[p.first] = min(p.second, freq2[p.first]);
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/find-common-characters/
/// Author : liuyubobobo
/// Time   : 2019-03-03

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;


/// Using MultiSet to get the intersection of every two strings
/// Time Complexity: O(n * ave_len_of_strings * log(ave_len_of_strings))
/// Space Complexity: O(n * ave_len_of_strings)
class Solution {
public:
    vector<string> commonChars(vector<string>& A) {

        vector<multiset<char>> sets(A.size());
        for(int i = 0; i < A.size(); i ++)
            for(char c: A[i])
                sets[i].insert(c);

        multiset<char> res = sets[0];
        for(int i = 1; i < sets.size(); i ++)
            res = intersection(res, sets[i]);

        vector<string> ret;
        for(char c: res)
            ret.push_back(string(1, c));
        return ret;
    }

private:
    multiset<char> intersection(multiset<char>& set1, multiset<char>& set2){

        multiset<char> res;
        for(char c: set1){
            multiset<char>::iterator iter = set2.find(c);
            if(iter != set2.end())
                res.insert(c), set2.erase(iter);
        }
        return res;
    }
};


void print_vec(const vector<string>& vec){
    for(const string& s: vec) cout << s << " ";
    cout << endl;
}

int main() {

    vector<string> A1 = {"bella","label","roller"};
    print_vec(Solution().commonChars(A1));

    return 0;
}