title: Efficient data structure for word lookup with wildcards
body: <p>I need to match a series of user inputed words against a large dictionary of words (to ensure the entered value exists).</p>
  
  <p>So if the user entered:</p>
  
  <pre><code>"orange" it should match an entry "orange' in the dictionary.
  </code></pre>
  
  <p>Now the catch is that the user can also enter a wildcard or series of wildcard characters like say</p>
  
  <pre><code>"or__ge" which would also match "orange"
  </code></pre>
  
  <p>The key requirements are:</p>
  
  <pre><code>* this should be as fast as possible.
  
  * use the smallest amount of memory to achieve it.  
  </code></pre>
  
  <p>If the size of the word list was small I could use a string containing all the words and use regular expressions. </p>
  
  <p>however given that the word list could contain potentially hundreds of thousands of enteries I'm assuming this wouldn't work.</p>
  
  <p>So is some sort of 'tree' be the way to go for this...?</p>
  
  <p>Any thoughts or suggestions on this would be totally appreciated!</p>
  
  <p>Thanks in advance,
  Matt</p>