Python – Substring presence in Strings List

Last Updated : 08 May, 2023

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 lists
test_list1 = ["Gfg", "is", "Best"]
test_list2 = ["I love Gfg", "Its Best for Geeks", "Gfg means CS"]
 
# printing original lists
print("The original list 1 : " + str(test_list1))
print("The original list 2 : " + str(test_list2))
 
# using loop to iterate
res = []
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))

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: 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 lists
test_list1 = ["Gfg", "is", "Best"]
test_list2 = ["I love Gfg", "Its Best for Geeks", "Gfg means CS"]
 
# printing original lists
print("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 Substrings
res = [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))

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]

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 lists
test_list1 = ["Gfg", "is", "Best"]
test_list2 = ["I love Gfg", "Its Best for Geeks", "Gfg means CS"]
 
# convert to sets and compute intersection
set1 = set(test_list1)
set2 = set(" ".join(test_list2).split())
intersection = set1.intersection(set2)
 
# convert intersection back to list
intersection_list = list(intersection)
 
# initialize result list
result = []
 
# check if each string in test_list1 is in the intersection list
for string in test_list1:
    if string in intersection_list:
        result.append(True)
    else:
        result.append(False)
 
# print result
print("The match list : " + str(result))

Output

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 arrays
arr1 = np.array(["Gfg", "is", "Best"])
arr2 = np.array(["I love Gfg", "Its Best for Geeks", "Gfg means CS"])
# printing original lists
print("The original list 1 : " + str(arr1))
print("The original list 2 : " + str(arr2))
# find if substring is present
res = np.array([any(np.char.find(arr2, i) != -1) for i in arr1])
 
# printing result
print("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.