Python – Convert List to key-value list by prefix grouping

Given a list, convert it to consecutive key-value lists, grouping by a prefix.

Input : test_list = ["GFG-1", 4, 6, "GFG-2", 3, "GFG-3", 9, 2], temp = "GF" 
Output : {'GFG-1': [4, 6], 'GFG-2': [3], 'GFG-3': [9, 2]} 
Explanation : All grouped till next prefix. 

Input : test_list = ["MRK-1", 4, 6, "MRK-2", 3, "MRK-3", 9, 2], temp = "MR" 
Output : {'MRK-1': [4, 6], 'MRK-2': [3], 'MRK-3': [9, 2]}
Explanation : All grouped till next prefix, "MR".

Method 1: Using groupby() + startswith() + lambda

The combination of the above functions can be used to solve this problem. In this, we employ grouping of all elements by prefix using groupby() and lambda functions to assist in performing segregation of prefix for grouping.

Step-by-step approach:

• Import the necessary module groupby from the itertools library.
• Define a list of elements named test_list.
• Print the original list test_list using the print() function.
• Define a string variable named temp and set it to “GFG”.
• Define an empty dictionary named res.
• Use the groupby() function to group the elements of the test_list by checking whether each element starts with the prefix temp. The lambda function is used to determine the starting prefix of each element.
• The results of the grouping are returned as a list of tuples containing two elements – the grouping key and a groupby object.
• Iterate over the list of tuples, and for each tuple, check if the key is true or false. If it’s true, extract the first element of the groupby object and assign it to the variable k. If it’s false, append the remaining elements of the groupby object to a list and assign the list as the value of the k key in the res dictionary.
• Print the resulting dictionary res using the print() function.

Below is the implementation of the above approach:

The original list : ['GFG-1', 4, 6, 7, 10, 'GFG-2', 2, 3, 'GFG-3', 9, 2, 4, 6]
The constructed dictionary : {'GFG-1': [4, 6, 7, 10], 'GFG-2': [2, 3], 'GFG-3': [9, 2, 4, 6]}

Time Complexity: O(n), where n is the elements of dictionary
Auxiliary Space: O(n), where n is the size of a dictionary

Method 2: Using defaultdict

Creates a defaultdict with the list as the default value type. Then, it iterates through the test_list and uses the string method startswith() to check if the element starts with the given prefix. If it does, it sets the key to the element. If not, it appends the element to the list associated with the current key in the defaultdict. Finally, it prints the resulting dictionary.

The constructed dictionary : defaultdict(<class 'list'>, {'GFG-1': [4, 6, 7, 10], 'GFG-2': [2, 3], 'GFG-3': [9, 2, 4, 6]})

Time complexity: O(n), where n is the length of the input list test_list.
Auxiliary space: O(n), because the resulting dictionary can have up to n/2 keys (in the worst case, when all elements in the list start with the prefix), and each key can have at most n/2 values (in the worst case when there are no elements starting with the prefix). 

Method 3: Using dictionary comprehension method to construct the dictionary

It iterates through the elements of the list using a ‘for’ loop and checks whether an element starts with the prefix string ‘temp’. If an element in the list starts with the prefix string ‘temp’, it initializes a new empty list as the value for the dictionary key corresponding to that element. If an element in the list does not start with the prefix string ‘temp’, it appends that element to the value list corresponding to the current dictionary key.

Since the program uses a ‘for’ loop to iterate through the elements of the list, it is not using the dictionary comprehension method. Rather, it is using a standard for loop to construct the dictionary.

Approach:

1. Initialize a list called ‘test_list‘ with multiple values of different data types.
2. Initialize a variable called ‘temp’ with a string “GFG” to search for the elements starting with this string.
3. Initialize an empty dictionary called ‘res‘ to store the elements from the list.
4. Iterate through the list using a ‘for‘ loop to check whether an element starts with the prefix string 
5. If an element in the list starts with the prefix string ‘temp‘, initialize a new empty list as the value for the dictionary key corresponding to that element.
6. If an element in the list does not start with the prefix string ‘temp‘, append that element to the value list corresponding to the current dictionary key.
7. After the loop completes, print the final constructed dictionary ‘res‘.

Below is the implementation of the above approach:

The constructed dictionary : {'GFG-1': [4, 6, 7, 10], 'GFG-2': [2, 3], 'GFG-3': [9, 2, 4, 6]}

Time Complexity: O(n), where ‘n’ is the number of elements in the list.
Auxiliary Space: O(n), where ‘n’ is the number of elements in the list, as we are creating a dictionary to store the elements of the list.

Method 4: Using loop + dictionary 

Approach:

1. Initialize an empty dictionary, res.
2. Initialize a variable key to an empty string.
3. Loop through the test_list:
4. If an element in the list starts with the prefix temp, update the key variable to the current element, and add an empty list to the dictionary with the current element as the key.
5. If the current element is not a string and does not start with the prefix, append it to the list of the currentkey in the dictionary.
6. Print the dictionary res.

The constructed dictionary : {'GFG-1': [4, 6, 7, 10], 'GFG-2': [2, 3], 'GFG-3': [9, 2, 4, 6]}

Time complexity: O(N), where n is the length of the input list.
Auxiliary space: O(N), as we need to store all the elements in the dictionary.

Method 5: Using list comprehension and slicing

Step-by-step approach:

• Initialize the list test_list.
• Print the original list.
• Initialize the prefix temp.
• Use list comprehension and slicing to get the indices where the prefix occurs. Store them in the indices list.
• Use dictionary comprehension to construct the dictionary. Iterate over the range of the length of indices and construct the key-value pairs using slicing. If the current index is less than the length of indices minus 1, slice the list from the current index plus 1 to the next index in indices. Otherwise, slice the list from the current index plus 1 to the end of the list.
• Print the constructed dictionary.

Below is the implementation of the above approach:

The original list : ['GFG-1', 4, 6, 7, 10, 'GFG-2', 2, 3, 'GFG-3', 9, 2, 4, 6]
The constructed dictionary : {'GFG-1': [4, 6, 7, 10], 'GFG-2': [2, 3], 'GFG-3': [9, 2, 4, 6]}

Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.