StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Build a <a href="http://en.wikipedia.org/wiki/Trie" rel="noreferrer">trie</a> of the words you have in the dictionary, which will make searching faster. Search the tree according to the following letters of your input string. When you've found a word, which is in the tree, recursively start from the position after that word in the input string. If you get to the end of the input string, you've found one possible fragmentation. If you got stuck, come back and recursively try another words.</p> <p>EDIT: sorry, missed the fact, that there must be just two words. In this case, limit the recursion depth to 2.</p> <p>The pseudocode for 2 words would be:</p> <pre><code>T = trie of words in the dictionary for every word in T, which can be found going down the tree by choosing the next letter of the input string each time we move to the child: p <- length(word) if T contains input_string[p:length(intput_string)]: return true return false </code></pre> <p>Assuming you can go down to a child node in the trie in <code>O(1)</code> (ascii indexes of children), you can find all prefixes of the input string in <code>O(n+p)</code>, where <code>p</code> is the number of prefixes, and <code>n</code> the length of the input. Upper bound on this is <code>O(n+m)</code>, where <code>m</code> is the number of words in dictionary. Checking for containing will take <code>O(w)</code> where <code>w</code> is the length of word, for which the upper bound would be <code>m</code>, so the time complexity of the algorithm is <code>O(nm)</code>, since <code>O(n)</code> is distributed in the first phase between all found words.</p> <p>But because we can't find more than <code>n</code> words in the first phase, the complexity is also limited to <code>O(n^2)</code>. So the search complexity would be <code>O(n*min(n, m))</code> Before that you need to build the trie which will take <code>O(s)</code>, where <code>s</code> is the sum of lengths of words in the dictionary. The upper bound on this is <code>O(n*m)</code>, since the maximum length of every word is <code>n</code>.</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