A (deceptively tricky?) Python question

I am writing a Scrabble AI, and I want to handle blank tiles. Right now, I want to expand a string containing blank tiles into a list of strings composed of words created by all possible interpretations of the blanks.

So, "H_LLO" ==> ["HALLO", "HBLLO", ... "HZLLO"] (length is 26)

However, Scrabble has 2 blank tiles, so I can't just do a simple for loop and replace.

For example, "H_LL_" ==> ["HALLA", "HALLB", ... "HBLLA", ... "HZLLZ"] (length is 26x26 = 676)

What is the cleanest way to do this? The best I could come up with is the following, but I don't much like it:

  import re
  from itertools import product

  w = "H_LL_"
  expanded = []
  product_args = list()
  for _ in xrange(w.count("_")):
      product_args.append( map(chr, range(65, 91)) )
  for repl_str in product(*tuple(product_args)):
      wtemp = w
      for c in repl_str:
          wtemp = re.sub('_', c, wtemp)
      expanded.append(wtemp)

Try this for when you need to fill 2 blank tiles:

  import string
  from itertools import product
  
  w = "H_LL_"
  w_fmt = w.replace('_', '%s')
  
  product_args = [list(string.uppercase)] * 2
  
  expanded = [w_fmt % repl for repl in product(*product_args)]

Yes, if you wanted to only have valid words, this could reduce the search space dramatically. I know it's not python, but if you replaced the '_'s with '.'s just the grep command will be surprisingly quick and powerful.

$ grep -i ^H.LL.$ /usr/share/dict/words

Maybe a similar method using the re module and then matching on your dictionary?

All possibilities with only two characters is still The reason is that internal Python operations are orders of magnitude faster than a looping construct where the loop is written in Python.

So I'd have a set for the allowed word list, generate a set of permutations and then ask Python for the intersection, rather than iterating through the permutations on the fly.

Here's another way to do this in Python.

   lets =  [chr(x) for x in range( ord('a'),ord('z')+1)]

   def blankexpand( templates ):
       expansion = []
       for t in templates:
        expansion = expansion + [t.replace('_',let,1) for let in lets]
       return expansion


   def expand( template ):
        blanktiles = template.count('_')
        if blanktiles == 0:
                print 'nothing to expand'
        elif blanktiles == 1:
                print blankexpand( [template] )
        elif blanktiles == 2:
                print blankexpand( blankexpand( [template] ) )
        else :
                print 'too many blank tiles'
        print


   expand( 'abce' )
   expand( 'a_')
   expand( 'h_ll_')
   expand( '___' )