Given list of substrings and list of string, check for each substring, if they are present in any of strings in List.
Input : test_list1 = [“Gfg”, “is”, “best”], test_list2 = [“I love Gfg”, “Its Best for Geeks”, “Gfg means CS”]
Output : [True, False, False]
Explanation : Only Gfg is present as substring in any of list String in 2nd list.Input : test_list1 = [“Gfg”, “is”, “best”], test_list2 = [“I love Gfg”, “It is Best for Geeks”, “Gfg means CS”]
Output : [True, True, False]
Explanation : Only Gfg and is are present as substring in any of list String in 2nd list.
Method #1 : Using loop
This is brute way in which this task can be performed. In this, we for, each element in list check if it’s substring of any of other list’s element.
Python3
# Python3 code to demonstrate working of # Substring presence in Strings List# Using loop# initializing liststest_list1 = ["Gfg", "is", "Best"]test_list2 = ["I love Gfg", "Its Best for Geeks", "Gfg means CS"]# printing original listsprint("The original list 1 : " + str(test_list1))print("The original list 2 : " + str(test_list2))# using loop to iterateres = []for ele in test_list1 : temp = False # inner loop to check for # presence of element in any list for sub in test_list2 : if ele in sub: temp = True break res.append(temp) # printing result print("The match list : " + str(res)) |
The original list 1 : ['Gfg', 'is', 'Best'] The original list 2 : ['I love Gfg', 'Its Best for Geeks', 'Gfg means CS'] The match list : [True, False, True]
Time complexity: O(nlogn), where n is the length of the test_list. The loop takes O(n*n) time
Auxiliary Space: O(n), extra space of size n is required
Method #2 : Using list comprehension + any()
The combination of above functions can be used to solve this problem. In this, we check for any sublist using any() and list comprehension is used to perform iteration.
Python3
# Python3 code to demonstrate working of # Substring presence in Strings List# Using list comprehension + any()# initializing liststest_list1 = ["Gfg", "is", "Best"]test_list2 = ["I love Gfg", "Its Best for Geeks", "Gfg means CS"]# printing original listsprint("The original list 1 : " + str(test_list1))print("The original list 2 : " + str(test_list2))# any() reduces a nesting# checks for element presence in all Substringsres = [True if any(i in j for j in test_list2) else False for i in test_list1]# printing result print("The match list : " + str(res)) |
The original list 1 : ['Gfg', 'is', 'Best'] The original list 2 : ['I love Gfg', 'Its Best for Geeks', 'Gfg means CS'] The match list : [True, False, True]
The Time and Space Complexity for all the methods are the same:
Time Complexity: O(n)
Space Complexity: O(n)
Method 3: using the built-in set and intersection functions.
steps to implement this approach:
- Convert both test_list1 and test_list2 to sets using the set function.
- Compute the intersection of the two sets using the intersection function.
- Convert the result back to a list using the list function.
- For each string in test_list1, check if it is in the resulting list from step 3.
- Append the result of the check to the final result list.
- Print the final result list.
Python3
# Python3 code to demonstrate working of # Substring presence in Strings List# Using set intersection# initializing liststest_list1 = ["Gfg", "is", "Best"]test_list2 = ["I love Gfg", "Its Best for Geeks", "Gfg means CS"]# convert to sets and compute intersectionset1 = set(test_list1)set2 = set(" ".join(test_list2).split())intersection = set1.intersection(set2)# convert intersection back to listintersection_list = list(intersection)# initialize result listresult = []# check if each string in test_list1 is in the intersection listfor string in test_list1: if string in intersection_list: result.append(True) else: result.append(False)# print resultprint("The match list : " + str(result)) |
The match list : [True, False, True]
Time complexity of this approach is O(n+m), where n is the length of test_list1 and m is the total length of all strings in test_list2.
The auxiliary space complexity is O(n+m) to store the sets and intersection.
Method 4: using numpy:
Algorithm:
- Import the required module numpy as np.
- Initialize two numpy arrays arr1 and arr2 with the given values.
- Print the original lists.
- Create a new numpy array res using list comprehension, where each element in the array is True if the
- corresponding element in arr1 is present in any element of arr2, False otherwise.
- Print the match list.
Python3
import numpy as np# initializing arraysarr1 = np.array(["Gfg", "is", "Best"])arr2 = np.array(["I love Gfg", "Its Best for Geeks", "Gfg means CS"])# printing original listsprint("The original list 1 : " + str(arr1))print("The original list 2 : " + str(arr2))# find if substring is presentres = np.array([any(np.char.find(arr2, i) != -1) for i in arr1])# printing resultprint("The match list : ", res)#This code is contributed by Vinay Pinjala |
Output: The original list 1 : ['Gfg' 'is' 'Best'] The original list 2 : ['I love Gfg' 'Its Best for Geeks' 'Gfg means CS'] The match list : [ True False True]
Time complexity:
The time complexity is O(nmk), where n is the length of arr1, m is the length of arr2, and k is the length of the longest string in arr2.
Space complexity:
The space complexity is O(nm), as we create a new numpy array with nm elements.
