Given a String list, map each character in strings, to indices it occurs.
Input : test_list = [‘g f g’, ‘b e s t’, ‘f o r’, ‘g e e k s’]
Output : {‘g’: [1, 4], ‘f’: [1, 3], ‘s’: [2, 4], ‘b’: [2], ‘e’: [2, 4], ‘t’: [2], ‘o’: [3], ‘r’: [3], ‘k’: [4]}
Explanation : Characters mapped with their occurring elements indices.Input : test_list = [‘g f g’, ‘i s’, ‘b e s t’, ‘f o r’, ‘g e e k s’]
Output : {‘g’: [1, 5], ‘f’: [1, 4], ‘i’: [2], ‘s’: [2, 3, 5], ‘b’: [3], ‘e’: [3, 5], ‘t’: [3], ‘o’: [4], ‘r’: [4], ‘k’: [5]}
Explanation : Characters mapped with their occurring elements indices.
Method #1 : Using defaultdict() + enumerate() + split()
The combination of above functions can be used to solve this problem. In this, we use defaultdict() to get empty list to store indices, enumerate() is used to check for indices and split() can be used for splitting characters.
step-by-step approach
- Import the defaultdict class from the collections module.
- Initialize the input list test_list as given in the problem statement.
- Print the original list for verification.
- Initialize a defaultdict object res with the default value set to an empty set.
- Use a loop to iterate over the elements of test_list and their corresponding indices using the enumerate() function.
- For each element, split it into sub-strings using the split() method and iterate over the resulting list of sub-strings.
- For each sub-string, add the current index (plus 1) to the set of indices associated with that sub-string in the res dictionary.
- Use a dictionary comprehension to convert the values in res from sets to lists.
- Print the resulting dictionary for verification.
Python3
# Python3 code to demonstrate working of # Charatacter indices Mapping in String List# Using defaultdict() + enumerate() + split()from collections import defaultdict# initializing listtest_list = ['g f g', 'i s', 'b e s t', 'f o r', 'g e e k s'] # printing original listprint("The original list is : " + str(test_list))res = defaultdict(set)# loop for assigning indicesfor idx, ele in enumerate(test_list): for sub in ele.split(): res[sub].add(idx + 1)# dictionary comprehension to remake result res = {key: list(val) for key, val in res.items()}# printing result print("The mapped dictionary : " + str(res)) |
The original list is : ['g f g', 'i s', 'b e s t', 'f o r', 'g e e k s']
The mapped dictionary : {'g': [1, 5], 'f': [1, 4], 'i': [2], 's': [2, 3, 5], 'b': [3], 'e': [3, 5], 't': [3], 'o': [4], 'r': [4], 'k': [5]}
Time complexity: O(n*m), where n is the number of elements in the list “test_list” and m is the average length of the sub-strings obtained by splitting the elements in “test_list”.
Auxiliary space: O(n*m), which is used to store the mapped indices in the dictionary “res”.
Method #2 : Using enumerate() + dictionary comprehension
This is another way in which this task can be performed. This performs task in similar way, just in one liner way in dictionary comprehension.
Python3
# Python3 code to demonstrate working of # Charatacter indices Mapping in String List# Using enumerate() + dictionary comprehension# initializing listtest_list = ['g f g', 'i s', 'b e s t', 'f o r', 'g e e k s'] # printing original listprint("The original list is : " + str(test_list))# using dictionary comprehension to bind resultres = {sub : [key + 1 for key, val in enumerate(test_list) if sub in val] for ele in test_list for sub in ele.split()}# printing result print("The mapped dictionary : " + str(res)) |
The original list is : ['g f g', 'i s', 'b e s t', 'f o r', 'g e e k s']
The mapped dictionary : {'g': [1, 5], 'f': [1, 4], 'i': [2], 's': [2, 3, 5], 'b': [3], 'e': [3, 5], 't': [3], 'o': [4], 'r': [4], 'k': [5]}
Time complexity: O(n^2), where n is the length of the longest string in the list.
Auxiliary space: O(n), where n is the total number of substrings in the list.
Method #3: Using join(),split(),list() and set() methods
Python3
# Python3 code to demonstrate working of# Charatacter indices Mapping in String List# initializing listtest_list = ['g f g','b e s t', 'f o r', 'g e e k s']# printing original listprint("The original list is : " + str(test_list))x=" ".join(test_list)x=x.split(" ")x=list(set(x))res=dict()for i in x: p=[] for j in test_list: if i in j: p.append(test_list.index(j)+1) res[i]=p# printing resultprint("The mapped dictionary : " + str(res)) |
The original list is : ['g f g', 'b e s t', 'f o r', 'g e e k s']
The mapped dictionary : {'k': [4], 'f': [1, 3], 'o': [3], 's': [2, 4], 'g': [1, 4], 't': [2], 'b': [2], 'e': [2, 4], 'r': [3]}
Time Complexity: O(n^2) where n is the length of the input list test_list.
Auxiliary Space: O(n) where n is the length of the input list test_list.
