String replacement with characters from Map to generate all possible combinations

String replacement with characters from Map to generate all possible combinations Given a hashmap M which is a mapping of characters to arrays of replacement characters, and an input string S, return an array of all possible combinations of S (where any character in S can be substituted with one of its substitutes in M, if it exists). What is the time complexity? What is the space complexity? Can you optimize either? Example input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [FaB, Fa8, 4aB, 4a8]

	# !/usr/bin/env python
	dictionary = { 'f': ['F', 4], 'b': ['B', 8, 9] }
	strg = "fab"
	#[FaB, Fa8, 4aB, 4a8]
	stack = list()
	results = list()
	char = ""
	def getResults(start_index):
	charu = strg[start_index]
	if charu in dictionary:
	for element in dictionary[charu]:
	stack.append(element)
	if start_index == len(strg)-1:
	results.append(''.join(map(str, stack)))
	stack.pop()
	continue
	getResults( start_index+1)
	else:
	stack.append( charu)
	getResults(start_index+1)
	if stack:
	stack.pop()
	else:
	return results
	print getResults( 0)

view raw str_pattern_1.py hosted with ❤ by GitHub