The classical problem that can be handled quite easily by python and has been also dealt with many times is finding if a string is substring of other. But sometimes, one wishes to extend this on list of strings and find how many strings satisfy condition, and hence then requires to traverse the entire container and perform the generic algorithm. Lets discuss certain ways to perform this task.
Method #1 : Using list comprehension + len() List comprehension is an elegant ways to perform any particular task as it increases readability in a long run. This task can be performed using naive method and hence can be reduced to list comprehension as well. The len() is used to compute length of list.
Python3
# Python code to demonstrate # Count Strings with substring String List# using list comprehension + len()# initializing list test_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']# printing original list print ("The original list is : " + str(test_list))# initializing substringsubs = 'Geek'# using list comprehension + len()# Count Strings with substring String Listres = len([i for i in test_list if subs in i])# printing result print ("All strings count with given substring are : " + str(res)) |
The original list is : ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are : 2
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 list “test_list”.
Method #2 : Using filter() + lambda + len() This function can also perform this task of finding the strings with the help of lambda. It just filters out all the strings matching the particular substring and then adds it in a new list. The len() is used to compute length of list.
Python3
# Python code to demonstrate # Count Strings with substring String List# using filter() + lambda + len()# initializing list test_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']# printing original list print ("The original list is : " + str(test_list))# initializing substringsubs = 'Geek'# using filter() + lambda + len()# Count Strings with substring String Listres = len(list(filter(lambda x: subs in x, test_list)))# printing result print ("All strings count with given substring are : " + str(res)) |
The original list is : ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are : 2
Time Complexity: O(n) where n is the number of elements in the string list. The sum() + generator expression is used to perform the task and it takes O(n) time.
Auxiliary Space: O(1) constant additional space needed
Method #3 : Using find() method
Approach
- Initiated a for loop to traverse the list
- Used the find() method to check whether the substring is present in each element of list
- If present increment the res variable
- Display the res variable
Python3
# Python code to demonstrate# Count Strings with substring String List# initializing listtest_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']# printing original listprint ("The original list is : " + str(test_list))# initializing substringsubs = 'Geek'# Count Strings with substring String Listres = 0for i in test_list: if i.find(subs)!=-1: res+=1# printing resultprint ("All strings count with given substring are : " + str(res)) |
The original list is : ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are : 2
Time Complexity : O(N)
Auxiliary Space : O(1)
Method #4 : Using operator.contains() method
Approach:
- Initiated a for loop to traverse the list
- Used the operator.contains() method to check whether the substring is present in each element of list
- If present increment the res variable
- Display the res variable
Python3
# Python code to demonstrate# Count Strings with substring String List# initializing listtest_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']# printing original listprint ("The original list is : " + str(test_list))# initializing substringsubs = 'Geek'# Count Strings with substring String Listres = 0import operatorfor i in test_list: if operator.contains(i,subs): res+=1# printing resultprint ("All strings count with given substring are : " + str(res)) |
The original list is : ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are : 2
Time Complexity : O(N)
Auxiliary Space : O(1)
Method #5: Using list comprehension + count()
This method uses list comprehension to generate a list of 1s and 0s based on whether the substring exists in each string. Then, sum() function is used to count the number of 1s in the list.
Python3
# Python code to demonstrate# Count Strings with substring String List# initializing listtest_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']# printing original listprint ("The original list is : " + str(test_list))# initializing substringsubs = 'Geek'# Count Strings with substring String Listres = sum(1 for s in test_list if s.count(subs)>0)# printing resultprint ("All strings count with given substring are : " + str(res)) |
The original list is : ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are : 2
Time complexity: O(n*m), where n is the length of the list and m is the length of the longest string in the list.
Auxiliary space: O(1) (excluding the space used to store the list)
Method #6: reduce() function from functools module:
Algorithm:
- Import reduce() function from functools module.
- Initialize the list of strings and the substring.
- Define a lambda function to check if the substring is present in the string.
- Use reduce() function to count the number of strings that contain the substring.
- Print the count of such strings.
Python3
from functools import reducetest_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']subs = 'Geek'# printing original listprint ("The original list is : " + str(test_list)) count = reduce(lambda x, y: x + 1 if subs in y else x, test_list, 0)# printing resultprint("All strings count with given substring are :", count)#This code is contributed by Jyothi pinjala. |
The original list is : ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are : 2
Time complexity: O(n), where n is the number of strings in the input list. This is because we need to iterate over each string in the list to check if the substring is present.
Space complexity: O(1). This is because we are only storing a few variables like the input list, substring, and the count of strings containing the substring. No new list or data structure is being created.
Method 7: using for loop
- Initialize the input list of strings test_list and print it.
- Initialize the substring subs.
- Initialize a counter variable count to zero.
- Use a for loop to iterate through each string in test_list.
- Check if the substring subs is present in the current string.
- If it is, increment the counter variable count.
- After the loop is finished, print the value of count.
Python3
# Python code to demonstrate # Count Strings with substring String List# using for loop# initializing list test_list = ['Lazyroar', 'Geeky', 'Computers', 'Algorithms']# printing original list print("The original list is: " + str(test_list))# initializing substringsubs = 'Geek'# using for loopcount = 0for string in test_list: if subs in string: count += 1# printing result print("All strings count with given substring are: " + str(count)) |
The original list is: ['Lazyroar', 'Geeky', 'Computers', 'Algorithms'] All strings count with given substring are: 2
time complexity of this method is O(nk), where n is the length of the list and k is the length of the substring. The auxiliary space required is O(1) because we are only using a counter variable.
