Checking If Combination Of Any Amount Of Strings Exists

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

Solution 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 = newRegExp('^(' + words.join('|') + ')*$');
sentences.forEach(sentence => {
    // search returns a position. It should be 0:console.log(sentence + ': ' + (sentence.search(regex) ? 'No' : 'Yes'));
});

But using regular expressions in an algorithm-challenge feels like cheating: you don't really write the algorithm, but rely on the regular expression implementation to do the job for you.

Without Regular Expressions

You could use this algorithm: first check whether a word matches at the start of the input sentence, and if so, remove that first occurrence from it. Then repeat this for the remaining part of the sentence. If this can be repeated until no characters are left over, you have a solution.

If characters are left over which cannot be matched with any word... well, then you cannot really conclude there is no solution for that sentence. It might be that some earlier made word choice was the wrong one, and there was an alternative. So to cope with that, your algorithm could backtrack and try other words.

This principle can be implemented through recursion. To gain memory-efficiency, you could leave the original sentence in-tact, and work with an index in that sentence instead.

The algorithm is implemented in arrow-function testString:

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

vartestString = (words, str, i = 0) =>
    i >= str.length || words.some( word =>
        str.substr(i, word.length) == word && testString(words, str, i + word.length)
    );
    
sentences.forEach(sentence => {
    console.log(sentence + ': ' + (testString(words, sentence) ? 'Yes' : 'No'));
});

Or, the same in non-arrow-function syntax:

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

var testString = function (words, str, i = 0) {
    return i >= str.length || words.some(function (word) {
        return str.substr(i, word.length) == word 
            && testString(words, str, i + word.length);
    });
}
sentences.forEach(function (sentence) {
    console.log(sentence + ': ' + (testString(words, sentence) ? 'Yes' : 'No'));
});

... and without some(), forEach() or ternary operator:

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

functiontestString (words, str, i = 0) {
    if (i >= str.length) returntrue;
    for (var k = 0; k < words.length; k++) {
         var word = words[k];
         if (str.substr(i, word.length) == word 
             && testString(words, str, i + word.length)) {
              returntrue;
         }
    }
}

for (var n = 0; n < sentences.length; n++) {
    var sentence = sentences[n];
    if (testString(words, sentence)) {
        console.log(sentence + ': Yes');
    } else {
        console.log(sentence + ': No');
    }
}

Solution 2:

Take the 4 words, put them into a regex. Use that regex to split each string. Take the length of the resulting array (subtract one for the initial length of one).

var size = 'thisis'.split(/this|is|my|dog/).length - 1

Or if your list of words is an array

var search = new RegExp(words.join('|'))
var size = 'thisis'.split(search).length - 1

Either way you are splitting up the string by the list of words you have defined.

---

You can sort the words by length to ensure that larger words are matched first by

words.sort(function (a, b) { return b.length - a.length })

Solution 3:

Here is the solution for anyone interested

var input = ['this','is','a','string']; // This will work for any input, but this is a test casevar orderedInput = input.sort(function(a,b){
    return b.length - a.length;
});
var inputRegex = newRegExp(orderedInput.join('|'));
// our combonation of words can be any size in an array, just doin this since prompt in js is spammyvar testStrings = ['thisis','thisisastring','thisisaduck','thisisastringg','stringg']; 
varfoundCombos  = (regex,str) => !str.split(regex).filter(str => str.length).length;
var finalResult = testStrings.reduce((all,str)=>{
    all[str] = foundCombos(inputRegex,str);
    if (all[str] === true){
        all[str] = 1;
    }
    else{
        all[str] = 0;
    }
    return all;
},{});
console.log(finalResult);