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

I'm try开发者_StackOverflow中文版ing 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].

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.

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.

Algorithm:

1. Break the target string into letters and group them, get count of each letter
2. Form all permutations of strings in the array, starting with 1 string and up to the entire array. If your string array is short (i.e. <32), you can have an auto-increment integer with bitmask to generate all the permutations. If your string array is long (>32), then use an array to store each "bit" slot with string length, and simulate incrementing integer.
3. Skip all permutations not of the same length as target string (this should eliminate 90% of all permutations). Get the total letter count by summing the number of "1" bits x length of string (or summing slots); it must = target string length.
4. For each permutation, breakdown down the letters and group them, get count of each letter
5. Run through the target string group letter by letter, compare count to the group of the string. The letters and counts must be exactly the same to succeed. If so, return that permutation as the answer.
6. Otherwise continue with another permutation
7. After going through all permutations, return fail.

A JavaScript implementation:

// Assume: target=target string, words_array=array of strings

function groupByLetters(map, text) {
    for (var x=0; x < text.length; x++) {
        var ch = text.charAt(x);
        var n = map[ch] || 0;
        map[ch] = n + 1;
    }
}

// Split the target string into letters

var target_map = {};
groupByLetters(target_map, target);

// Create permutation slots

var slots = [];

for (var x=0; x < words_array.length; x++) {
    // Now in order to optimize speed, store the length of each string in the slot
    // Negative = not selected, positive = selected
    slots.push(-words_array[x].length);
}

// Loop through all permutations

while(true) {
    var carry = true;
    var plength = 0;

    for (var x=0; x < slots.length; x++) {
        var slen = slots[x];
        if (carry) {
            if (slen < 0) {     // Bit 0
                carry = false;
                slots[x] = -slen;   // 0->1, no carry
            } else {
                slots[x] = -slen;   // 1->0, continue to carry
            }
        }

        if (slots[x] > 0) plength += slots[x];
    }

    if (carry) {    // We have exhausted the permutations
        return null;
    }

    // Now plength = total number of letters in selected permutation

    if (plength !== target.length) continue;    // Not the same number of letters, skip

    // Build map of all letters in selected permutation

    var pmap = {};
    var permutation = [];

    for (var x=0; x < slots.length; x++) {
        if (slots[x] > 0) {
            groupByLetters(pmap, words_array[x]);
            permutation.push(words_array[x]);
        }
    }

    // Check if the map is the same as the target map

    var match = true;

    for (var letter in target_map) {
        if (!target_map.hasOwnProperty(letter)) continue;
        if (target_map[letter] !== pmap[letter]) {
            match = false;
            break;
        }
    }

    if (match) return permutation;  // Success!
}

Caveat: I have not tried running this. Let me know if I made a typo here or there.

See example here →

var wordInDict = function ( word, dict ) {
    var dict = dict.slice(0), // copy dict to not mutate original
        wl = word.length,
        dl = dict.length,
        i, j, diw,
        wCount = 0;

    for (i = 0; i < wl; i++) {
        for (j = 0; j < dl; j++) {
            diw = dict[j].indexOf(word[i]); // is letter of word in dict word
            if (diw > -1) {
                wCount++;

                // remove used character from dictionary
                if (diw == dict[j].length-1) {
                    dict[j] = dict[j].slice(0, diw);
                } else if (diw == 0) {
                    dict[j] = dict[j].slice(1);
                } else {
                    dict[j] = dict[j].slice(0,diw) + 
                              dict[j].slice(diw+1,dict[j].length-1);
                }

                // letter found, so move to next letter in target word
                break;
            }
        }
    }

    return wCount == wl;
};

var tW = 'dodge';
var tD = ['god','house','d','e','cat','c','r','jump'];
var tE = ['got','house','d','e','cat','c','r','jump'];
console.log(wordInDict(tW, tD)); // true
console.log(wordInDict(tW, tE)); // false

I just realized that this problem is equivalent to the subset product problem, and therefore NP-Complete.

Let s(x) be a size method that it returns an integer for every string by mapping the characters to prime numbers and then returning the product of these prime numbers:

a --> 2, b --> 3, c --> 5, d --> 7, e --> 11, etc.

Then we get

s("abc") = 2 * 3 * 5 = 30 = 5 * 2 * 3 = s("cab")

Given a dictionary A, we are now looking for a subset A'⊂ A such that the product

p = ∏ { s(a) : a ∈ A' }

equals s(key) for a given key.

Two solutions possibly I can think of

1. Sort the given strings using Array.sort() and if sorted array matches then boom strings are anagrams.

2. Wrote a piece of native code

   function permutable(input1,input2) { if(typeof input1 === 'string' && typeof input2 === 'string' ) { const array_1 = input1.split('') const array_2 = input2.split('') let count2 = 0; let count1 = 0 let is_permutable = false if(array_1.length === array_2.length) { for(let j =0;j<array_1.length;j++) { count1 = checkrepeatations(array_1[j],array_1) if(array_2.includes(array_1[j])) { count2 = checkrepeatations(array_1[j],array_2) }else { return false; }

        if(count1 === count2) {
            is_permutable = true;
        } else {
          is_permutable = false;
        }
      }
      if(is_permutable) {
        return true;
      } else {
        return false;
      }
    } else {
      return false
    }
   
    }else {
      return false;
    }
   

   }

   function checkrepeatations(word,array_1) { let count = 0; let i =0; // array_1[j] = t and t e s t while(i<array_1.length) { //array_1[i] = t if(word === array_1[i]) { count++; } i++ } return count; }

P.S Learning to code, so any suggestions on memory/variable management are appreciated.