A (deceptively tricky?) Python question

  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)]

So for your example, you start at the H node and follow all paths. Then follow the L path if it exists. Then follow the next L path. Then follow all paths from that node. Then check if the word has ended.

   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( '___' )

Another almost as trivial solution would be to have a string with two blanks and permute away !

If you want all possibilities, I might suggest wrapping it in a function that can lazily return the possibilities one by one as needed (see the yield keyword).

If you want only valid entries, you will probably want something more sophisticated (e.g. a search tree)