Sometimes, while workings with data, we can have a problem in which we need to perform a merge of digits. This is a simpler problem. But it becomes complex once we need to perform merger of certain elements like numbers that are too consecutive. Let’s discuss certain ways in which this task can be performed.
Method #1: Using list comprehension + groupby() + isdigit()
The combination of the above functions can be used to perform this task. In this, we first group all the digits consecutive and then perform the concatenation.
Python3
# Python3 code to demonstrate # Merge Consecutive digits Strings# using list comprehension + groupby() + isdigit()from itertools import groupby# Initializing listtest_list = ['gfg', '1', '2', 'is', '5', 'best', '6', '7']# printing original listprint("The original list is : " + str(test_list))# Merge Consecutive digits Strings# using list comprehension + groupby() + isdigit()res = [sub for i, j in groupby(test_list, str.isdigit) for sub in ([''.join(j)] if i else j)]# printing result print ("List after digit merge : " + str(res)) |
The original list is : ['gfg', '1', '2', 'is', '5', 'best', '6', '7'] List after digit merge : ['gfg', '12', 'is', '5', 'best', '67']
Time Complexity: O(N) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(N), where n is the number of elements in the new res list
Method #2 : Using regex + join()
The combinations of the above functions can also be used to deal with this. In this, we find the digits using regex function and perform merger using join(). Works only with single characters.
Python3
# Python3 code to demonstrate# Merge Consecutive digits Strings# using regex() + join()import re# Initializing listtest_list = ['g', '1', '2', 'i', '5', 'b', '6', '7']# Printing original listprint("The original list is : " + str(test_list))# Merge Consecutive digits Strings# using regex() + join()res = re.findall('\d+|.', ''.join(test_list))# Printing resultprint("List after digit merge : " + str(res)) |
The original list is : ['g', '1', '2', 'i', '5', 'b', '6', '7'] List after digit merge : ['g', '12', 'i', '5', 'b', '67']
Method 3: Using Iteration and Concatenation
Python3
# Merging consecutive digits# using Iteration and Concatenationdef merge_consecutive_digits(lst): res = [] temp = '' for i in lst: if i.isdigit(): temp += i else: if temp: res.append(temp) temp = '' res.append(i) if temp: res.append(temp) return res# Input listtest_list = ['gfg', '1', '2', 'is', '5', 'best', '6', '7']# Print statemensprint("The original list is :", test_list)print("List after digit merge:", merge_consecutive_digits(test_list)) |
The original list is : ['gfg', '1', '2', 'is', '5', 'best', '6', '7'] List after digit merge: ['gfg', '12', 'is', '5', 'best', '67']
Time complexity: O(N), where n is the length of the input list.
Space complexity: O(N), where n is the length of the input list.
Explanation: The function merge_consecutive_digits takes a list as input and iterates through each element. If the current element is a digit, it concatenates it to a temporary string. If the current element is not a digit, it appends the temporary string to the result list, if the temporary string is not empty, and then resets the temporary string. Finally, if the temporary string is not empty, it appends it to the result list.
Method 4: Using the built-in reduce() function.
Steps:
- Initialize the input list test_list.
- Check if the test_list is not empty.
- Use the reduce() function to iterate over the elements of the test_list.
- In each iteration, check if the current element y is a digit and the last element of the accumulator list x is also a digit.
- If the above condition is true, then merge the current element y with the last element of the accumulator list x.
- If the above condition is not true, then append the current element y to the accumulator list x.
- Return the final accumulator list x after all iterations.
- If the test_list is empty, return an empty list.
Python3
# import reduce() functionfrom functools import reduce# Initializing listtest_list = ['gfg', '1', '2', 'is', '5', 'best', '6', '7']# Printing original listprint("The original list is : " + str(test_list))# Merge Consecutive digits Strings using reduce() functionif test_list: res = reduce(lambda x, y: x[:-1] + [x[-1] + y] if x and isinstance( x[-1], str) and x[-1].isdigit() and y.isdigit() else x + [y], test_list, [])else: res = []# Printing resultprint("List after digit merge : " + str(res))# This code contributed by tvsk |
The original list is : ['gfg', '1', '2', 'is', '5', 'best', '6', '7'] List after digit merge : ['gfg', '12', 'is', '5', 'best', '67']
Time complexity: O(N), where n is the length of the input list test_list. The reduce() function iterates over all the elements of the list once.
Auxiliary space: O(N), where n is the length of the input list test_list. The accumulator list x can grow up to the size of the input list test_list.
Method 5:Using a recursive function
Steps:
- Define the function merge_consecutive_digits(lst) that takes a list lst as input.
- Check if the input list is empty. If it is, return an empty list.
- Check if the first element of the list is a digit. If it is, find the index i of the next non-digit element in the list.
- Slice the input list from index 0 up to index ‘i’, and join the resulting sublist into a single string.
- Recursively call the merge_consecutive_digits() function on the remainder of the input list starting from index i. Concatenate the string from step 4 with the result of the recursive call from step 5.
- If the first element of the input list is not a digit, return a list containing the first element concatenated with the result of a recursive call to merge_consecutive_digits() on the remainder of the input list starting from the index.
- Combine the results of the recursive calls in steps 5 and 7 into a single list.
- Return the final list.
Python3
def merge_consecutive_digits(lst): if not lst: return [] if lst[0].isdigit(): i = 1 while i < len(lst) and lst[i].isdigit(): i += 1 # Merge consecutive digits return [''.join(lst[:i])] + merge_consecutive_digits(lst[i:]) else: return [lst[0]] + merge_consecutive_digits(lst[1:])# Input list test_list = ['gfg', '1', '2', 'is', '5', 'best', '6', '7']# printing input list print("The original list is : " + str(test_list))res = merge_consecutive_digits(test_list)# Printitng list after mergingprint("List after digit merge : " + str(res))# This code is contributed by Jyothi pinjala |
The original list is : ['gfg', '1', '2', 'is', '5', 'best', '6', '7'] List after digit merge : ['gfg', '12', 'is', '5', 'best', '67']
Time complexity: O(n), where n is the length of the input list. This is because each element of the list is visited exactly once during the recursive function call.
Auxiliary Space: O(n), because the function call stack can grow up to the size of the input list in the worst case when all elements are digits. In addition, the function creates new lists during concatenation and slicing, which adds to the space complexity. However, the size of these lists is proportional to the size of the input list, so the space complexity is still O(n).
Method 6: Method 6: Using a stack
- Initialize an empty stack.
- Traverse the input list from left to right.
- If the current element is a digit and the stack is not empty, and the top element of the stack is also a digit, then pop the top element of the stack and append it to the current digit.
- Otherwise, push the current element onto the stack.
- After traversing the entire input list, pop all the remaining elements from the stack and append them to the output list.
- Return the output list.
Python3
def merge_consecutive_digits(lst): stack = [] res = [] for i in range(len(lst)): if lst[i].isdigit() and stack and stack[-1].isdigit(): stack[-1] += lst[i] else: stack.append(lst[i]) while stack: res.append(stack.pop()) return res[::-1]# Input list test_list = ['gfg', '1', '2', 'is', '5', 'best', '6', '7']# Printing original list print("The original list is : " + str(test_list))res = merge_consecutive_digits(test_list)# Printing list after merging print("List after digit merge : " + str(res)) |
The original list is : ['gfg', '1', '2', 'is', '5', 'best', '6', '7'] List after digit merge : ['gfg', '12', 'is', '5', 'best', '67']
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 (worst case, when there are no consecutive digits).
