Given list of phrases, extract all the Strings with begin with character K.
Input : test_list = [“Gfg is good for learning”, “Gfg is for Lazyroar”, “I love G4G”], K = l
Output : [‘learning’, ‘love’]
Explanation : All elements with L as starting letter are extracted.Input : test_list = [“Gfg is good for learning”, “Gfg is for Lazyroar”, “I love G4G”], K = m
Output : []
Explanation : No words started from “m” hence no word extracted.
Method #1 : Using loop + split()
This is brute way in which this problem can be solved. In this, we convert each phrase into list of words and then for each word, check if it’s initial character is K.
Python3
# Python3 code to demonstrate working of# Extract words starting with K in String List# Using loop + split()# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"res = []for sub in test_list: # splitting phrases temp = sub.split() for ele in temp: # checking for matching elements if ele[0].lower() == K.lower(): res.append(ele)# printing resultprint("The filtered elements : " + str(res)) |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(n*n), where n is the size of list
Auxiliary Space: O(n), where n is the size of list
Method #2 : Using list comprehension + split()
This is yet another way in which this task can be performed. In this we run double nested loops inside single list comprehension and perform required conditional checks.
Python3
# Python3 code to demonstrate working of# Extract words starting with K in String List# Using list comprehension + split()# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"res = [ele for temp in test_list for ele in temp.split() if ele[0].lower() == K.lower()]# printing resultprint("The filtered elements : " + str(res)) |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(n2)
Auxiliary Space: O(n)
Method #3 : Using split(),extend(),lower() and find() methods
Python3
# Python3 code to demonstrate working of# Extract words starting with K in String List# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"res = []x = []for i in test_list: x.extend(i.split())for j in x: if j.lower().find(K) == 0: res.append(j)# printing resultprint("The filtered elements : " + str(res)) |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(n*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 #4 : Using startswith(),upper() and lower() methods
Python3
# Python3 code to demonstrate working of# Extract words starting with K in String List# Using loop + split()# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"res = []x = []for i in test_list: x.extend(i.split())for i in x: if(i.startswith(K) or i.startswith(K.lower()) or i.startswith(K.upper())): res.append(i)# printing resultprint("The filtered elements : " + str(res)) |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n*n) where n is the number of elements in the list “test_list”.
Method #4 : Using lambda functions, extend(), lower() methods
Python3
# Python3 code to demonstrate working of# Extract words starting with K in String List# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"res = []for i in test_list: words = i.split() startWords = list(filter(lambda x: x[0].lower() == K.lower(), words)) res.extend(startWords)# printing resultprint("The filtered elements : " + str(res)) |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Method #5 : Using itertools.filterfalse() functions
Python3
# Python3 code to demonstrate working of# Extract words starting with K in String Listimport itertools# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"res = []for i in test_list: words = i.split() startWords = list(itertools.filterfalse(lambda x: x[0].lower() != K.lower(), words)) res.extend(startWords)# printing resultprint("The filtered elements : " + str(res)) |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Method #6:Using reduce()
- Import the reduce() function from the functools module.
- Initialize the list of strings test_list and the character K.
- Use reduce() with a lambda function that takes two arguments x and y.
- Split each string y in the list into words and filter the words that start with the character K.
- Append the filtered words to the accumulator list x.
- Initialize the initial value of the accumulator as an empty list [].
- The final result list will be the value returned by the reduce() function.
- Print the final result list.
Python3
# importing reduce modulefrom functools import reduce# initializing listtest_list = ["Gfg is best", "Gfg is for Lazyroar", "I love G4G"]# printing original listprint("The original list is : " + str(test_list))# initializing KK = "g"# Extract words starting with K in String List# Using reduce() + split()res = reduce(lambda x, y: x + [ele for ele in y.split() if ele[0].lower() == K.lower()], test_list, [])# printing resultprint("The filtered elements : " + str(res))#This code is contributed by Vinay Pinjala. |
The original list is : ['Gfg is best', 'Gfg is for Lazyroar', 'I love G4G'] The filtered elements : ['Gfg', 'Gfg', 'Lazyroar', 'G4G']
Time Complexity: O(n*m)
where n is the number of strings in test_list and m is the maximum number of words in any string.
The time complexity of split() is O(m) and the time complexity of filtering words starting with K is also O(m).
Since this process is done for each string in test_list, the overall time complexity is O(n*m).Space Complexity: O(n*m)
The space complexity is dominated by the list filtered_words which stores the filtered words.
The maximum size of this list can be n*m, if all the words in test_list start with the character K.
The space complexity of reduce() is O(m) because it only stores the intermediate result (the list of filtered words) during each iteration.
Therefore, the overall space complexity is O(n*m).
