6
\$\begingroup\$

Given two strings, find the common characters.

Is there better implementation for this problem?

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

std::string   find_intersection(std::string & first, std::string & second)
{
   std::sort(std::begin(first),std::end(first));
   std::sort(std::begin(second), std::end(second));
   int length = std::min(first.length(), second.length());
   std::string result(length,' ');
   std::set_intersection(std::begin(first),std::end(first),std::begin(second),std::end(second),std::begin(result));

   result.shrink_to_fit();
   return result; 
}

int main()
{
   std::string first="GermanTown";
   std::string second="Georgia";
    std::cout<<find_intersection(first,second)<<"\n";
   return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I have to agree with the other two. Using algorithms is the correct way to go. But this can be done in O(n) if your character set is only 255 members (ie your string is not UTF-8 encoded). Its a classic trade space for time optimizations. \$\endgroup\$ – Martin York Apr 1 '15 at 16:34
7
\$\begingroup\$

For the same reasons as @DJanssens, I would like to compliment you for a simple and clean algorithm making proper use of the standard library. That may seem basic, but there are too many people ignoring the standard <algorithm> in the world, so I'm glad that you decided to use it. I only want to add two more things:

  • First, I don't think that shrink_to_fit will do what you expect it to do. When you construct result, you allocate memory and fill it with spaces, so result's size probably grew to. shrink_to_fit will get rid of the allocated but unused memory, but it won't get rid of the extra spaces that you allocated at construction.

  • What you can do is default-construct your std::string and use an std::back_inserter to fill it the lazy way. The std::back_inserter will perform some magic so that the result's push_back method is called whenever an element has to be added:

    std::string find_intersection(std::string & first, std::string & second)
    {
        std::sort(std::begin(first),std::end(first));
        std::sort(std::begin(second), std::end(second));
    
        std::string result;
    
        std::set_intersection(
            std::begin(first), std::end(first),
            std::begin(second), std::end(second),
            std::back_inserter(result)
        );
    
        return result; 
    }
    
\$\endgroup\$
  • \$\begingroup\$ I like this answer because of its insight on my mistakes. All answers are good but let me choose this one. \$\endgroup\$ – Steephen Apr 3 '15 at 5:04
3
\$\begingroup\$

I like your algorithm. It's easy, readable and works!

In addition it is also fast. Using the sort approach, makes your time complexity around O(n*log(n)).

But can we go faster?

Well it all depends on your problem statement. Do you have to process extremely large input (Asymptotic complexity)?

I just want to show you another approach, where you do not use the built-in std functions and that runs in O(n). One might argue that it's not necessary in your case and that this approach brings other overheads for saving only log-n performance. Still, it might be useful to give an alternative view.

Let's show this with an example:

String1 = lolly  
String2 = lolp

it should return that they have in common: l = 2, o = 1

We could use two arrays/Maps. Depending if you are allowed to use built in datastructures. (If you only consider ASCII characters the arrays should be 128 integers long.)

You first run over the first string, which is done in O(n). For each character in the string you add 1 to the representative in the first array/Map. You do the same for the second string and store this in the second array/Map.

this results in:

String1 => l = 3, o = 1, y = 1
String2 => l = 2, o = 1, p = 1

By taking the min() for each entry (considering absence of the char in one of the strings = 0), you end up with the common characters.

result => l = 2, o = 1, y = 0, p = 0

This all should be able to be done in 3 non-nested for loops, resulting in O(n)


What about the coding style?

First of all I have to compliment you on the use of std::, (We discussed this question in chat. (Feel free to join us))

You should however consider using space after a comma:

std::set_intersection(std::begin(first),std::end(first),std::begin(second),std::end(second),std::begin(result));

vs.

std::set_intersection(std::begin(first), std::end(first), std::begin(second), std::end(second), std::begin(result));

Goodluck!

\$\endgroup\$
  • \$\begingroup\$ Thanks DJanssens for your answer and invite to chat room, I am around there sometimes!! +1 \$\endgroup\$ – Steephen Apr 3 '15 at 5:06
2
\$\begingroup\$

I like your algorithm better (using the STL algorithms correctly).

But an O(n) solutions:

Try: (may have some bugs I did not test).

std::string   find_intersection(std::string & first, std::string & second)
{
    int   one[255] = {0};
    int   two[255] = {0};
    std::for_each(std::begin(first), std::end(first),   [](char c){one[static_cast<unsigned char>(c)]++;});
    std::for_each(std::begin(second), std::end(second), [](char c){two[static_cast<unsigned char>(c)]++;});

    std::string result;
    for(int loop=0; loop < 256;++loop)
    {
        if (one[loop] > 0 && two[loop] > 0)
        {
            result.push_back(loop);
        }
     }
     return result;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks @Loki Astari for the answer. Appreciate the effort to present here a better piece of code!! +1 \$\endgroup\$ – Steephen Apr 3 '15 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.