Javascript: Check if string can be re-created by combining other strings in an array?

Question

I'm trying to figure out the best way to check whether a particular string can be created by combining other strings that I have in an array. The other strings can be any length, including one character. Furthermore, the characters in the other strings can be reordered.

So if we were looking for the word "dodge" and our array of strings was ['god','house','d','e','cat','c','r','jump'], we would have a match, since we could combine the letters in 'god','d', and 'e' to create 'dodge'.

If the array contained "dot" instead of "d", we would not have a match, since we have to use all the characters in each of the words we recombine (we'd have to use 'o' and 't' as well).

I would also like to know which words were used to create the specified word, so if there is a match I want the function to return the array indexes of the words that were recombined to create the specified word. For the "dodge" example above it would return [0,2,3].

Answer 1

EDIT
This should be much faster than the naive solution, because all the work is being done by the built-in indexOf search which is really fast, plus it can quit on the first mismatch.

function match(array, word){
    var char_array = word.split(''),
        char, index;
    array = array.join('').split('');
    while(char_array.length > 0){
        char = char_array.shift();
        if ((index = array.indexOf(char)) > -1)
            array.splice(index, 1);
        else
            return false;
    }
    return true;
}

This is the naive solution:

function match(array, word){
    var char_array = word.split(''),
        array_elem;
    //loop over array
    for(var i=0, l=array.length; i < l; i++){
        array_elem = array[i].split('');
            //loop over the remaining chars in the word and
            //cross-check with the current array element
        for (var j=0,len =  char_array.length,index; j < len; j++)
            if ((index = array_elem.indexOf(char_array[j])) > -1){
                //char matched, remove it from both arrays
                char_array.splice(j, 1);
                array_elem.splice(index, 1);
            }
        }
    if(char_array.length < 1) return true
        else return false
}

There should be optimizations that can be done to make it faster, if that was an issue.

Answer 2

I wrote a solution that has worst case O(2^n), but it will perform quite well in most situations. I started with a function that maps each string to an object that counts all the different letters in the string. Example:

map("dodge") --> { "d": 2, "e": 1, "g": 1, "o": 1, size: 5 }

As you can see, it also stores the size in the result. This is the implementation:

function map(str) {
    var obj = { size: str.length };

    for(var i=0; i<str.length; i++) {   
        var ch = str.charAt(i);
        obj[ch] = (ch in obj) ? obj[ch]+1 : 1;
    }

    return obj;
}

Then I write a function that "subtracts" two mapped objects. For example:

subtract(map("ab"), map("a")) --> { "b": 1, size: 1 }
subtract(map("dodge"), map("god")) --> { "d": 1, "e": 1, size: 1 }
subtract(map("abc"), map("abc")) --> { size: 0 }
subtract(map("a"), map("b")) --> null

As you can see in the last example, the function returns null if subtraction is not possible. This is an implementation for subtract:

function subtract(a, b) {
    var result = { size: 0 };

    for(var i=97; i<123; i++) { // from a to z (ASCII)
        var ch = String.fromCharCode(i);
        var diff = (a[ch] || 0) - (b[ch] || 0);

        if(diff < 0)
            return null;

        if(diff > 0) {
            result[ch] = diff;
            result.size += diff;
        }
    }
    return result;
}

The last step is writing a method findCombination(word, dict) that returns a combination if it finds any, or else null. Examples:

var dict = ['god','house','d','e','cat','c','r','jump'];
findCombination("dodge", dict) --> [0, 2, 3]
findCombination("housecat", dict) --> [1, 4]
findCombination("hose", dict) --> null
findCombination("xyz", dict) --> null

I use a recursive method with backtracking where I try to "subtract" words from the given key until the result is "empty":

var findCombination = function(word, dict)
{
    var solution = [];
    var mappedDict = [];

    for(var i=0; i<dict.length; i++)
        mappedDict[i] = map(dict[i]);           

    var recursiveFind = function(key,  i)
    {
        if(i == mappedDict.length)
            return false;

        var result = subtract(key, mappedDict[i])

        if(result == null)
            return recursiveFind(key, i+1);

        solution.push(i);

        if(result.size == 0 || recursiveFind(result, i+1))
            return true;

        solution.pop();
        return recursiveFind(key, i+1);
    };

    if(recursiveFind(map(word), 0))
        return solution;

    return null;
};

You could (and should) optimize the code by initializing the mappedDict variable only once, instead of every time findCombination() is invoked.