Last Updated: 7 Mar, 2021
Longest Word
Moderate
Asked in companies
You are given an array/list of words ‘ARR’. Your task is to find all the words having the longest length which can be made from some other words on the list.
Note :
Return the list of all those words sorted in alphabetical. Return an empty list in case there are no such words
For Example :
Input: cat, banana, dog, nana, my, walk, walker, baby, dogwalkers, s, babymybaby
Output: babymybaby dogwalkers
Here in the given list of words, you can see that the words babymybaby, dogwalkers contain the words present in the list i.e. ‘s’, 'dog’, ‘walker’,‘baby’ and ‘my’ and both are of the same length.
Input format :
The first line contains the integer 'N', denoting the number of words that you will be given. Then N lines follow.
Each of the next 'N' lines contains a word denoting the elements of the word ARR.
Output format :
For the given list of ‘N’ words, print all such words in lexicographical order.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= N <= 1000
1 <= length of longest word <= 100
Where ‘N’ is the given list of words.
Time limit: 1 second
Approaches
The key observation here is to notice a simple fact that the longest word would be the one whose substring splits in all possible ways are also present in the list.
The algorithm for the same can be as follows:-
Steps:
- Sort the elements (words) given in the list in descending order of their lengths (arrange them lengthwise)
- Store the sorted elements in the list in a Set (having only unique strings)
- Now start with the first string and loop over sorted strings.
- While Iterating in the list of words recursively, check whether the words when divided into different possible substrings are also present in the set where all unique strings are stored.
- Return True from the recursive check if some part of the substring from the word is present in the set and recursively continue checking the same for the remaining part. Call the recursive function on the remaining part of the substring to make sure that the word is comprised of all substrings present in the list as well.
- Otherwise, if there are substrings in the word which are not present in the list then, return False.
- We finally add the longest such words obtained from the list and add them to another list.
- Return the final list of words sorted in alphabetical order.
Similar problems