check if a string can be made from characters in another string

Question

I want to check if string1 can be made by taking characters from string2 and putting them in the right order. What would be the most effective way to do that?

For example, I have 2 strings as shown below:

string s1 = "ABCDASFSADFAF", s2 ="ABCDFGSAGSRASFSFASFASDADFAFDSAGFAS";

as you can see, we can make string s1 from the characters in string s2, so string1 exists in string2. So basically, I need to check if you can make string s1 from string s2. what would be the most effective way to do something like that? I had an idea, to go through with loop, and check how many times each letter is in string, and then do the same with second string, then just compare the array's with stored information, and if string s2 letter array has more or equal to string s1 array letters, then we will be able to make s1 from s2.

Oh and programming language is C++.

score 3 · Answer 1 · answered Feb 23 '12 at 20:31

3

Sort each string (std::sort) then use std::includes.

answered Feb 23 '12 at 20:31

Alan Stokes

18,815
3
45
64

score 0 · Accepted Answer · answered Feb 23 '12 at 14:09

You can check for this by looping through s1 and removing the first find of each character from a copy of s2:

#include <string.h>

using namespace std;

string s1 = "ABCC", s2 = "DCBA";

string copy = s2;
size_t found;
bool contains = true;

for(int i = 0; i < s1.length(); i++)
{
    found = copy.find(s1[i]);
    if(found == string::npos)
    {
        contains = false;
        break;
    }
    copy = copy.replace(found, 1, "");
}

// Now 'contains' is true if s1 can be made from s2, false if it can't.
// If also 'copy' is empty, s1 is an anagram of s2.

check if a string can be made from characters in another string

2 Answers2