How to intersect of more than 2 arrays?

user_18112546 0
Viewed 79

I would like to intersect of more than 2 arrays. Here's incomplete version of my coding :

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    int n;

    cin >> n;
    cout << "\n";

    string rock[n];

    for(int i=0;i<n;i++)
    {
        cin >> rock[i];
        cout << "\n";
    }

    for(int i=0;i<n;i++)
        sort(rock[i].begin(), rock[i].end());

}

So for example if I input

3
asasadfg
aassdw
dasaasf

I want it the output to be like this

ads

No duplication and intersect between more than 2 arrays. What's the best way to do it? Thanks

c++
2 Answers

Note: Variable length arrays are not standard in C++ and at best are a compiler-specific feature. In this case because length is not known at compile time, you'd be best off using a std::vector.

Now, we just need to know how to find the intersection of two strings, and do that across the entire vector. I'm sure there's a more elegant way, but hopefully you can trace what's happening below.

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

int main() {
    int n;

    std::cin >> n;
    std::cout << "\n";

    std::vector<std::string> rocks;

    for (int i = 0; i < n; ++i) {
        std::string temp;
        std::cin >> temp;
        rocks.push_back(temp);
        std::cout << "\n";
    }

    for (auto &s : rocks) {
        std::sort(s.begin(), s.end());
    }

    std::string diff = rocks[0];

    for (int i = 1; i < n; ++i) {
        std::string temp_diff;

        std::set_intersection(
            diff.begin(), diff.end(), 
            rocks[i].begin(), rocks[i].end(),  
            std::back_inserter(temp_diff));

        diff = temp_diff;
    }

    auto last = std::unique(diff.begin(), diff.end());
    diff.erase(last, diff.end());

    std::cout << diff << std::endl;

    return 0; 
}
user_152613150
  1. Insert the values in the first array into an output_set.
  2. Go through the next array and if the element is in the output_set, store it in a new_set.
  3. swap(new_set, output_set), clear the new_set
  4. If there is a next array, go to step 2.
  5. The repeated items are in the output set.

If the items are sorted, the intersection in step 2 can be done more efficiently without using sets.

user_60503640
Related