Sometimes, while working with String lists, we can have a problem in which we need to perform all possible concatenations of all the strings that occur in list. This kind of problem can occur in domains such as day-day programming and school programming.
Let’s discuss a way in which this task can be performed.
Input : test_list = [‘Gfg’, ‘Best’]
Output : [‘Gfg’, ‘Best’, ‘GfgBest’, ‘BestGfg’]Input : test_list = [‘Gfg’]
Output : [‘Gfg’]
Method 1: Using permutations() + join() + loop
The combination of above functions can be used to solve this problem. In this, we perform the task of concatenation using join() and all possible combination extraction using permutations().
Python3
# Python3 code to demonstrate working of # All possible concatenations in String List# Using permutations() + loopfrom itertools import permutations# initializing listtest_list = ['Gfg', 'is', 'Best']# printing original list print("The original list : " + str(test_list))# All possible concatenations in String List# Using permutations() + looptemp = []for idx in range(1, len(test_list) + 1): temp.extend(list(permutations(test_list, idx)))res = []for ele in temp: res.append("".join(ele))# printing result print("All String combinations : " + str(res)) |
The original list : ['Gfg', 'is', 'Best'] All String combinations : ['Gfg', 'is', 'Best', 'Gfgis', 'GfgBest', 'isGfg', 'isBest', 'BestGfg', 'Bestis', 'GfgisBest', 'GfgBestis', 'isGfgBest', 'isBestGfg', 'BestGfgis', 'BestisGfg']
Time complexity: O(n*n!) where n is the length of the input list.
Auxiliary Space: O(n*n!) where n is the length of the input list. The space complexity is dominated by the number of permutations that are generated and stored in the temporary list temp.
Method – 2: Using recursion and concatenation:
Approach:
- Define a helper function helper(lst, i, j) that takes the input list lst and two indices i and j and performs the following steps:
- If i is equal to the length of the list lst, then we have reached the end of the list and we return a list containing the string at index j.
- If j is equal to the length of the list lst, then we have reached the end of a pass through the list and need to move on to the next index i by calling the helper function again with i+1 and 0 as the new indices.
- If i and j are not equal, then we concatenate the strings at indices i and j and add the resulting string to a list, along with the results of a recursive call to the helper function with the same i and j+1 indices.
- If i and j are equal, then we simply call the helper function again with the same i and j+1 indices.
- Finally, we return the results of calling the helper function with initial indices 0 and 0, concatenated with the original input list.
Below is the implementation of the above approach:
Python3
# Python program for the above approach# Function to generate all possible combination# using recursiondef concat_list4(lst): def helper(lst, i, j): if i == len(lst): return [lst[j]] if j == len(lst): return helper(lst, i+1, 0) if i != j: return [lst[i] + lst[j]] + helper(lst, i, j+1) return helper(lst, i, j+1) return helper(lst, 0, 0) + lst# Driver Code# Test case 1test_list1 = ['Gfg', 'Best']output1 = concat_list4(test_list1)print(output1) # Output: ['Gfg', 'Best', 'GfgBest', 'BestGfg']# Test case 2test_list2 = ['Gfg']output2 = concat_list4(test_list2)print(output2) # Output: ['Gfg'] |
['GfgBest', 'BestGfg', 'Gfg', 'Gfg', 'Best'] ['Gfg', 'Gfg']
Time Complexity: O(N2)
Space Complexity: O(N2)
