Subset strings

[znerich]

So I am making this game kinda like super text twist. I was wondering if there are functions in c++ that lets you know if the guess word is a subset of the scrambled word. Of course, the number of characters would have to match up.

Example

word || scambled word || guess
1.hello || olhel || loo
2.hello || olhel || ole



1.this should be invalid since there is only one 'o' in the original
2. this should be valid since only one 'l' is used up.


Any help, please? It's ok if you will not give a code, just some ideas on how to do this will do. Thanks.

[JLBorges]

A simple (not the most efficient) way to do this would be:

a. Lexicographically order the two sequences (ignoring case, I suppose).

std::string make_key( std::string str )
{
    std::for_each( str.begin(), str.end(), [] ( char& c ) { c = std::toupper(c) ; } ) ; // C++11
    std::sort( str.begin(), str.end() ) ;
    return str ;
}

b. Do a linear search to check if a sorted sequence is a proper subsequence of another sorted sequence .

bool is_sub_sequence( const std::string& sorted_seq, const std::string& sorted_subseq )
{
    std::size_t pos = 0 ;
    for( std::size_t i = 0 ; i < sorted_subseq.size() ; ++i )
    {
        pos = sorted_seq.find( sorted_subseq[i], pos ) ;
        if( pos == std::string::npos ) return false ;
        else ++pos ;
    }
    return true ;
}

c. Put them together to get the function:

bool is_partial_word( const std::string& word, const std::string& guess )
{ return is_sub_sequence( make_key(word), make_key(guess) ) ; }

[znerich]

JLBorges, are these separate methods or step by step? Thanks by the way:)

[JLBorges]

I would prefer to write the code in three separate functions. (Which is what I've done in the snippet above).