StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I wrote a solution that has worst case <code>O(2^n)</code>, 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:</p> <pre><code>map("dodge") --> { "d": 2, "e": 1, "g": 1, "o": 1, size: 5 } </code></pre> <p>As you can see, it also stores the size in the result. This is the implementation:</p> <pre><code>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; } </code></pre> <p>Then I write a function that "subtracts" two mapped objects. For example:</p> <pre><code>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 </code></pre> <p>As you can see in the last example, the function returns <code>null</code> if subtraction is not possible. This is an implementation for <code>subtract</code>:</p> <pre><code>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; } </code></pre> <p>The last step is writing a method <code>findCombination(word, dict)</code> that returns a combination if it finds any, or else null. Examples:</p> <pre><code>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 </code></pre> <p>I use a recursive method with backtracking where I try to "subtract" words from the given key until the result is "empty":</p> <pre><code>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; }; </code></pre> <p>You could (and should) optimize the code by initializing the <code>mappedDict</code> variable only once, instead of every time <code>findCombination()</code> is invoked.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload