javascript - Checking if combination of any amount of strings exists

Question

I'm solving a puzzle and I have an idea of how to solve this problem, but I would like some guidance and hints.

Suppose I have the following, Given n amount of words to input, and m amount of word combos without spaces, I will have some functionality as the following.

    4
    this
    is
    my
    dog
    5
    thisis        // outputs 1
    thisisacat    // 0, since a or cat wasnt in the four words
    thisisaduck   // 0, no a or cat
    thisismy      // 1 this,is,my is amoung the four words
    thisismydog   // 1

My thoughts

First What I was thinking of doing is storing those first words into an array. After that, I check if any of those words is the first word of those 5 words

Example: check if this is in the first word thisis. It is! Great, now remove that this, from thisis to get simply just is, now delete the original string that corresponded to that equality and keep iterating over the left overs (now is,my,dog are available). If we can keep doing this process, until we get an empty string. We return 1, else return 0!

Are my thoughts on the right track? I think this would be a good approach (By the way I would like to implement this in javascript)

Answer 1

Sorting words from long to short may in some cases help to find a solution quicker, but it is not a guarantee. Sentences that contain the longest word might only have a solution if that longest word is not used.

Take for instance this test case:

Words: toolbox, stool, boxer
Sentence: stoolboxer

If "toolbox" is taken as a word in that sentence, then the remaining characters cannot be matched with other valid words. Yet, there is a solution, but only if the word "toolbox" is not used.

Solution with a Regular Expression

When regular expressions are allowed as part of the solution, then it is quite simple. For the above example, the regular expression would be:

^(toolbox|stool|boxer)*$

If a sentence matches that expression, it is a solution. If not, then not. This is quite straightforward, and doesn't really require an algorithm. All is done by the regular expression interpreter. Here is a snippet:

var words = ['this','is','a','string'];
var sentences = ['thisis','thisisastring','thisisaduck','thisisastringg','stringg']; 

var regex = new RegExp('^(' + words.join('|') + ')*$');
sentences.forEach(sentence => {
    // search returns a position. It should be 0:
    console.log(sentence + ': ' + (sentence.search(regex) ? 'No' : 'Yes'));
});