I can bail out of branches of combinations if the info so far won’t fit, but that still leads me to visiting every valid combination which in one of the examples is 500k.
By "every valid combination" do you mean every substitution of '?' with a '#' or '.'? If yes, then you're wrong, you can bail out of branches that don't fit early, and cut a lot of them this way.
Consider the following example:
???????????? [1, 2, 2]
When you substitute the first two question marks with ##
, the answer already doesn't match the input string, so you can throw away 1M of the combinations that don't fit.
Also, while you're at it, avoid generic type annotations (e.g. list
), try to always specify the generic argument (e.g. list[str]
) :)