Sometimes, we need to filter the list with the first character of each string in the list. This type of task has many applications in day-day programming and even in the competitive programming domain. Let’s discuss certain ways in which this task can be performed.
Method #1 : Using list comprehension + startswith() In this method, we use list comprehension for traversal logic and the startswith method to filter out all the strings that starts with a particular letter. The remaining strings can be used to make a different list.
Python3
# Python3 code to demonstrate# Prefix Separation# Using list comprehension + startswith()# initializing listtest_list = ['sapple', 'orange', 'smango', 'grape']# initializing start Prefixstart_letter = 's'# printing original listprint("The original list : " + str(test_list))# using list comprehension + startswith()# Prefix Separationwith_s = [x for x in test_list if x.startswith(start_letter)]without_s = [x for x in test_list if x not in with_s]# print resultprint("The list without prefix s : " + str(without_s))print("The list with prefix s : " + str(with_s)) |
The original list : ['sapple', 'orange', 'smango', 'grape'] The list without prefix s : ['orange', 'grape'] The list with prefix s : ['sapple', 'smango']
The time complexity of the above code is O(n), where n is the number of elements in the input list test_list.
The auxiliary space complexity of the code is O(n) as well, because the two output lists with_s and without_s may have up to n elements combined.
Method #2 : Using filter() + lambda + startswith() This task can be performed using the filter function with performs the similar task internally as the above function and lambda is helper function to build the logic.
Python3
# Python3 code to demonstrate# Prefix Separation# Using filter() + startswith() + lambda# initializing listtest_list = ['sapple', 'orange', 'smango', 'grape']# initializing start Prefixstart_letter = 's'# printing original listprint("The original list : " + str(test_list))# using filter() + startswith() + lambda# Prefix Separationwith_s = list(filter(lambda x: x.startswith(start_letter), test_list))without_s = list(filter(lambda x: not x.startswith(start_letter), test_list))# print resultprint("The list without prefix s : " + str(without_s))print("The list with prefix s : " + str(with_s)) |
The original list : ['sapple', 'orange', 'smango', 'grape'] The list without prefix s : ['orange', 'grape'] The list with prefix s : ['sapple', 'smango']
Time Complexity: O(n), where n is the number of elements in the input list test_list.
Auxiliary Space: O(n) as well, because the two output lists with_s and without_s may have up to n elements combined.
Method #3 : Without using startswith()
Python3
# Python3 code to demonstrate# Prefix Separation# initializing listtest_list = ['sapple', 'orange', 'smango', 'grape']# initializing start Prefixstart_letter = 's'# printing original listprint("The original list : " + str(test_list))# Prefix Separationwith_s = []without_s = []for i in test_list: if(i[0]==start_letter): with_s.append(i) else: without_s.append(i)# print resultprint("The list without prefix s : " + str(without_s))print("The list with prefix s : " + str(with_s)) |
The original list : ['sapple', 'orange', 'smango', 'grape'] The list without prefix s : ['orange', 'grape'] The list with prefix s : ['sapple', 'smango']
Time Complexity: O(n), where n is the number of elements in the input list test_list.
Auxiliary Space: O(n) as well, because the two output lists with_s and without_s may have up to n elements combined.
Method #4 : Using find() method
Python3
# Python3 code to demonstrate# Prefix Separation# initializing listtest_list = ['sapple', 'orange', 'smango', 'grape']# initializing start Prefixstart_letter = 's'# printing original listprint("The original list : " + str(test_list))# Prefix Separationwith_s = []without_s = []for i in test_list: if(i.find(start_letter)==0): with_s.append(i) else: without_s.append(i)# print resultprint("The list without prefix s : " + str(without_s))print("The list with prefix s : " + str(with_s)) |
The original list : ['sapple', 'orange', 'smango', 'grape'] The list without prefix s : ['orange', 'grape'] The list with prefix s : ['sapple', 'smango']
Time complexity: O(M^N) as the number of combinations generated is M choose N.
Auxiliary space: O(M^N) as the size of the resultant list is also M choose N.
Method #5 : Using re.findall() and re.compile()
We can use regular expressions to filter the list elements starting with a given prefix. The regular expression uses the ^ symbol to match the start of the string and [] to match a specific character or range of characters.
Python3
import re# initializing listtest_list = ['sapple', 'orange', 'smango', 'grape']# initializing start prefixstart_letter = 's'# printing original listprint("The original list : " + str(test_list))# Using regular expressions to filter list elements starting with prefixwith_s = [x for x in test_list if re.match(r'^{}'.format(start_letter), x)]without_s = [x for x in test_list if x not in with_s]# print resultprint("The list without prefix s : " + str(without_s))print("The list with prefix s : " + str(with_s))#This code is contributed by Edula Vinay Kumar Reddy |
The original list : ['sapple', 'orange', 'smango', 'grape'] The list without prefix s : ['orange', 'grape'] The list with prefix s : ['sapple', 'smango']
The time complexity of the above regular expression code is O(n) where n is the number of elements in the list. This is because we are iterating through each element in the list once and performing a regular expression match on each element. The space complexity is also O(n) as we are creating two separate lists, one for elements that match the prefix and one for elements that don’t match the prefix, and each of these lists can contain up to n elements in the worst case scenario where all elements in the original list match the prefix or none of the elements match the prefix.
