cresjoy cresjoy - 4 months ago 12
Javascript Question

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 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

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'));
});

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']; 

var testString = (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'));
});