StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've encountered similar problems when writing a crossword editor (e.g., find all words of length 5 with a 'B' in second position). Basically it comes down to:</p> <ul> <li>Process a word list and organize words by length (i.e., a list of all words of length 2, length 3, length 4, etc). The reason is that you often know the length of the word(s) that you wish to search for. If you want to search for words of unknown length, you can repeat a search again for a different word list. </li> <li>Insert each separate word list into a <a href="https://en.wikipedia.org/wiki/Ternary_search_tree" rel="nofollow">tertiary search tree</a> which makes searching for words a lot faster. Each node in the tree contains a character and you can descend the tree to search for words. There are also specialized data structures such as a <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow">trie</a> but I have not (yet) explored.</li> </ul> <p>Now for your problem, you could use the search tree to write a search function such as</p> <pre><code>function findWords($tree, $letters) { // ... } </code></pre> <p>where <code>tree</code> is the search tree containing the words of the length that you wish to search for and <code>letters</code> is a list of valid characters. In your example, <code>letters</code> would be the string <code>efjlnrrttuwx</code>. </p> <p>The search tree allows you to search for words, one character at a time, and you can keep track of characters that you have encountered so far. As long as these characters are in the list of valid letters, you keep searching. Once you've encountered a leaf node in the search tree, you have found an existing word which you can add to the result. If you encounter a character which is not in <code>letters</code> (or it has already been used), you can skip that word and continue the search elsewhere in the search tree.</p> <p>My crossword editor <a href="https://bitbucket.org/svisser/palabra" rel="nofollow">Palabra</a> contains an implementation of the above steps (a part is done in Python but mostly in C). It works fast enough for Ubuntu's default word list containing roughly 70K words.</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