[zephjc]

Well, do you really want ALL possibilities, or just valid ones (actual words - HZLLO is not a word)?

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)

[retrogradeorbit]

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?

[rlpb]

All possibilities with only two characters is still <1000 combinations. At this sort of small number I'd take a guess and say that it would be quicker to use a slightly less efficient algorithm and let the Python internals do the processing on lists than to iterate at Python level.

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.