Given a Strings list, extract all the strings that are a combination of K substrings.
Input : test_list = [“neveropen4u”, “allbest”, “abcdef”], substr_list = [“s4u”, “est”, “al”, “ge”, “ek”, “def”], K = 3
Output : [‘neveropen4u’]
Explanation :neveropen4u made up of 3 substr – ge, ek and s4u.
Input : test_list = [“neveropen4u”, “allbest”, “abcdef”], substr_list = [“s4u”, “est”, “al”, “ge”, “def”, ‘lb’], K = 3
Output : [‘allbest’]
Explanation : allbest made up of 3 substr – al, lb and est.
Method #1 : Using permutations() + map() + join() + set() + loop
In this, we perform this task by getting all possible permutation of K substrings from substring list, and then perform task of join using join and map(). The set() is used to avoid duplication. At last, match from Strings list is done using loop.
Python3
# Python3 code to demonstrate working of # Filter Strings combination of K substrings# Using permutations() + map() + join() + set() + loopfrom itertools import permutations# initializing listtest_list = ["neveropen4u", "allbest", "abcdef"]# printing stringprint("The original list : " + str(test_list))# initializing substring listsubstr_list = ["s4u", "est", "al", "ge", "ek", "def", "lb"]# initializing K K = 3# getting all permutationsperms = list(set(map(''.join, permutations(substr_list, r = K))))# using loop to check permutations with listres = []for ele in perms: if ele in test_list: res.append(ele)# printing results print("Strings after joins : " + str(res)) |
The original list : ['neveropen4u', 'allbest', 'abcdef'] Strings after joins : ['neveropen4u', 'allbest']
Method #2 : Using intersection()
This uses all functions of the above method, the last task of matching permutation list and original list is done by intersection.
Python3
# Python3 code to demonstrate working of # Filter Strings combination of K substrings# Using permutations() + map() + join() + set() + intersection()from itertools import permutations# initializing listtest_list = ["neveropen4u", "allbest", "abcdef"]# printing stringprint("The original list : " + str(test_list))# initializing substring listsubstr_list = ["s4u", "est", "al", "ge", "ek", "def", "lb"]# initializing K K = 3# getting all permutationsperms = set(map(''.join, permutations(substr_list, r = K)))# using intersection() to solve this problem res = list(set(test_list).intersection(perms))# printing results print("Strings after joins : " + str(res)) |
The original list : ['neveropen4u', 'allbest', 'abcdef'] Strings after joins : ['neveropen4u', 'allbest']
The Time and Space Complexity for all the methods are the same:
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3: Using nested loops to generate permutations and checking for matches.
Algorithm:
1. Import the `permutations()` function from `itertools`.
2. Define the given `test_list`, `substr_list`, and `K`.
3. Initialize an empty list `res`.
4. Loop through each string `s` in `test_list`.
5. Loop through each permutation `p` of length `K` in `substr_list`.
6. Check if the joined permutation `p` is a substring of the current string `s`.
7. If it is, append the string `s` to the `res` list and break out of the loop over permutations.
8. Print the resulting list `res` of strings that contain at least one combination of `K` substrings from `substr_list`.
Python3
from itertools import permutationstest_list = ["neveropen4u", "allbest", "abcdef"]substr_list = ["s4u", "est", "al", "ge", "ek", "def", "lb"]K = 3print("The original list : " + str(test_list))res = []for s in test_list: for p in permutations(substr_list, K): if ''.join(p) in s: res.append(s) breakprint("Strings after joins : " + str(res)) |
The original list : ['neveropen4u', 'allbest', 'abcdef'] Strings after joins : ['neveropen4u', 'allbest']
The time complexity of this algorithm is O(n*k! * m), where n is the length of `test_list`, k is the length of each permutation (which is a constant `K` in this case), and m is the maximum length of any string in `test_list`.
The auxiliary space of this algorithm is also O(n * m), since we need to store the resulting list `res` of strings that match the condition. The space complexity of the `permutations()` function is O(k!), which is a constant.
