Given a list of words and a positive integer K, write a Python program to find k longest words in the list in descending order of length. Examples:
Input : lst = ['am', 'watermelon', 'girl', 'boy', 'colour'], K = 3 Output : ['watermelon', 'colour', 'girl'] Input : ['see', 'I', 'geek', 'on', 'brain'], K = 4 Output : ['brain', 'geek', 'see', 'on']
Method #1 : Using count() from itertools First, sort the ‘lst’ based on length of the words and then based on a counter variable, so that words occurring later gets higher priority and thus, extract k variables.
Python3
# Python3 program to Find # longest K words in a listfrom itertools import countdef longest_word(lst, K): cnt = count() return sorted(lst, key = lambda w : (len(w), next(cnt)), reverse = True)[:K]# Driver codelst = ['am', 'watermelon', 'girl', 'boy', 'colour']K = 3print(longest_word(lst, K)) |
['watermelon', 'colour', 'girl']
Method #2 : Using sorted()
Python3
# Python3 program to Find # longest K words in a listdef longest_word(lst, K): idx, words = zip(*sorted(enumerate(lst), key = lambda w: (-len(w[1]), -w[0]))[:K]) return list(words)# Driver codelst = ['am', 'watermelon', 'girl', 'boy', 'colour']K = 3print(longest_word(lst, K)) |
['watermelon', 'colour', 'girl']
Method #3 : Using heap
Python3
# Python3 program to Find # longest K words in a listimport heapqfrom operator import itemgetterdef longest_word(lst, K): # constructing heap heap = [(0, i, '') for i in range(K)] heapq.heapify(heap) # To maintain top K elements for i, word in enumerate(lst): item = (len(word), i, word) if item > heap[0]: heapq.heapreplace(heap, item) return sorted(list(map(itemgetter(2), heap)), key = len, reverse = True)# Driver codelst = ['am', 'watermelon', 'girl', 'boy', 'colour']K = 3print(longest_word(lst, K)) |
['watermelon', 'colour', 'girl']
Method#4: Sort and slice
Approach
this approach involves sorting the given list of words in decreasing order of length of the words, and then returning the first k words of the sorted list. This can be implemented in Python using the sorted() function and list slicing.
Algorithm
1. Sort the given list of words in decreasing order of length of the words.
2. Return the first k words of the sorted list.
Python3
def find_k_longest_words(lst, k): sorted_lst = sorted(lst, key=len, reverse=True) return sorted_lst[:k]lst = ['am', 'watermelon', 'girl', 'boy', 'colour']k = 3print(find_k_longest_words(lst, k)) |
['watermelon', 'colour', 'girl']
Time Complexity: O(nlogn) – sorting the list takes nlogn time where n is the number of words in the list. Slicing the list takes O(k) time.
Space Complexity: O(n) – the sorted list takes up n space.
METHOD 5: Using a for loop and a list: This program finds the k-longest words in a given list using an iterative approach.
- Initialize an empty list longest_words to store the k longest words.
- Iterate through each word in the given list.
- If longest_words is empty, add the word to the list.
- Otherwise, compare the length of the current word with the length of each word in longest_words.
- If the length of the current word is greater than the length of a word in longest_words, insert the current word at that index and break the loop.
- If the loop completes without inserting the current word, and the length of longest_words is less than k, append the current word to longest_words.
- If the length of longest_words is greater than k, remove the shortest word from longest_words.
- After iterating through all words in the list, longest_words will contain the k longest words.
Python3
# Python program for the above approach# Given Listlst = ['am', 'watermelon', 'girl', 'boy', 'colour']k = 3# Stores the longest wordslongest_words = []for word in lst: if not longest_words: longest_words.append(word) else: for i, long_word in enumerate(longest_words): if len(word) > len(long_word): longest_words.insert(i, word) break else: if len(longest_words) < k: longest_words.append(word) if len(longest_words) > k: longest_words.pop() # Print the resultsprint(longest_words) |
['watermelon', 'colour', 'girl']
Time Complexity: O(n*k) where n is the number of words in the list.
Space Complexity: O(k) to store the k longest words in the longest_words list.
NumPy approach to find k longest words in a given list:
Algorithm:
Convert the list of words to a NumPy array.
Get the lengths of all the words using the numpy.vectorize() method.
Sort the NumPy array based on the word lengths in descending order.
Get the first k words of the sorted array and return them as a list.
Python3
import numpy as npdef find_k_longest_words(lst, k): # Convert list to numpy array arr = np.array(lst) # Get the length of each word get_len = np.vectorize(len) lengths = get_len(arr) # Sort array based on word lengths sorted_arr = arr[np.argsort(lengths)[::-1]] # Get the first k words and return them as a list return sorted_arr[:k].tolist() # Driver codelst = ['am', 'watermelon', 'girl', 'boy', 'colour']k = 3print(find_k_longest_words(lst, k)) |
Output:
[‘watermelon’, ‘colour’, ‘girl’]
Time complexity: O(nlogn), where n is the number of words in the list. Sorting the array takes nlogn time.
Auxiliary Space: O(n), where n is the number of words in the list. The numpy array takes up n space.
