Given a String and dictionary with characters mapped to replacement characters values list, construct all possible strings after replacing present characters with mapped values.
Input : test_str = “Lazyroar”, test_dict = {‘s’ : [‘1’, ‘5’], ‘k’ : [‘3’]}
Output : [‘gee31’, ‘geek1’, ‘gee35’, ‘geek5’, ‘gee3s’, ‘Lazyroar’]
Explanation : All possible replacement of strings, e.g in ‘gee35’, k is replaced by ‘3’ and s is replaced by ‘5’.Input : test_str = “Lazyroar”, test_dict = {‘s’ : [‘1’], ‘k’ : [‘3’]}
Output : [‘gee31’, ‘geek1’, ‘gee3s’, ‘Lazyroar’]
Explanation : All possible replacement of strings, e.g in ‘gee31’, k is replaced by ‘3’ and s is replaced by ‘1’.
Method #1: Using zip() + list comprehension + replace() + product()
The combination of the above functions can be used to solve this problem. In this, we extract all the combination characters using product and pair one at a time using zip(), and replacement using replace().
Python3
# Python3 code to demonstrate working of# Character Replacement Combination# Using zip() + list comprehension + replace() + product()from itertools import product# initializing stringtest_str = "Lazyroar"# printing original stringprint("The original string is : " + str(test_str))# initializing dictionarytest_dict = {'s': ['1', '2'], 'k': ['3']}# adding original character to possible charactersfor key in test_dict.keys(): if key not in test_dict[key]: test_dict[key].append(key)res = []# constructing all possible combination of values using product# mapping using zip()for sub in [zip(test_dict.keys(), chr) for chr in product(*test_dict.values())]: temp = test_str for repls in sub: # replacing all elements at once using * operator temp = temp.replace(*repls) res.append(temp)# printing resultprint("All combinations : " + str(res)) |
The original string is : Lazyroar All combinations : ['gee31', 'geek1', 'gee32', 'geek2', 'gee3s', 'Lazyroar']
Time Complexity: O(n3)
Auxiliary Space: O(n)
Method #2: Using recursion
- Define a recursive function that takes in the original string, the dictionary of character replacements, a list to store the results, and a string to store the current combination.
- If the original string is empty, append the current combination to the list of results.
- If the original string is not empty, get the first character of the original string and remove it from the string.
- If the character is in the dictionary, iterate over its possible replacements and call the function recursively with the remaining string and the current combination concatenated with each replacement.
- If the character is not in the dictionary, call the function recursively with the remaining string and the current combination concatenated with the original character.
- Return the list of results.
Python3
def get_combinations(original_str, replacements_dict, results_list, current_combination): if not original_str: results_list.append(current_combination) else: first_char = original_str[0] remaining_str = original_str[1:] if first_char in replacements_dict: for replacement in replacements_dict[first_char]: get_combinations(remaining_str, replacements_dict, results_list, current_combination + replacement) else: get_combinations(remaining_str, replacements_dict, results_list, current_combination + first_char)# Example usage:test_str = "Lazyroar"print("The original string is : " + str(test_str))test_dict = {'s': ['1', '2'], 'k': ['3']}for key in test_dict.keys(): if key not in test_dict[key]: test_dict[key].append(key)res = []get_combinations(test_str, test_dict, res, "")print("All combinations : " + str(res)) |
The original string is : Lazyroar All combinations : ['gee31', 'gee32', 'gee3s', 'geek1', 'geek2', 'Lazyroar']
Time complexity: O(2^n), where n is the length of the original string, in the worst case when all characters have multiple possible replacements.
Auxiliary space: O(n*m), where n is the length of the original string and m is the maximum number of possible replacements for a single character, due to the recursion stack.
