Replace '#' in a string with a set of characters, give all possible string combinations

Question

Question :
Replace '#' in a string S with a set of characters. Generate all possible string combinations after replacing.

Example 1:
string = "a#b"
set of char = {1,2,3}
possible strings are "a1b", "a2b", "a3b"

Example 2:
string = "##b"
set of char = {1,2}
possible strings are "11b", "22b", "12b", "21b"

My work:
With single '#' it is evident, and I am able to do, but when the string is like "a#bcd#ef#", I am not getting an idea to proceed with.

Would someone please provide an algorithm and working code(possibly in python)

Answer 1

You can use itertools.product to generate the possible string combinations, and then use an iterator (and next) trick to replace # with characters.

import itertools

def fill_pounds(s, chars):
    for p in map(iter, itertools.product(chars, repeat=s.count('#'))):
        yield ''.join(c if c != '#' else next(p) for c in s)

print(*fill_pounds('a#b', '123'))
print(*fill_pounds('##b', '12'))
print(*fill_pounds('f##k', 'or'))

Output:

a1b a2b a3b
11b 12b 21b 22b
fook fork frok frrk