All possible values that will match a regular expression
A major inefficiency in your solution is that you try every fill_in character as a replacement for any character class in the pattern. Instead, you could use the character class to select matching characters from fill_in and only loop over those. 

&gt;&gt;&gt; pattern = 'K0[2468]'
&gt;&gt;&gt; re.findall(expression, pattern)
['[2468]']
&gt;&gt;&gt; re.findall('[2468]', fill_in)
['2', '4', '6', '8']


For a more complete existing solution, you may want to look into these:


Regular expression parsing in Python
invRegex.py in Pyparsing examples