String pattern generation based on Dictionary entries

Given a string as input, return the list of all the possible patterns: ''' { "1" : ['A', 'B', 'C'], "2" : ['D', 'E'], "12" : ['X'], "3" : ['P', 'Q'] } ''' Example if input is "123", then output is ["ADP","ADQ","AEP","AEQ","BDP","BDQ","BEP","BEQ","CDP","CDQ","CEP","CEQ","XP","XQ"]