Last Updated: 30 Dec, 2020
Rearrange Sentences
Easy
Asked in company
You are given an array of ‘N’ sentences. Each sentence is a space-delimited string of words. The first word in each sentence is an alphanumeric identifier. Then, at least one of the following conditions will hold true:
1. After identifier, each word will consist only of lowercase English letters
2. After the identifier, each word will consist only of numbers.
We will call these two types of sentences, letter – sentence and number– sentence. It is guaranteed that each sentence has at least one word after its identifier. Your task is to sort these sentences such that the following two conditions will hold.
1. All letter - sentences must come before number- sentences.
2. The letter - sentences must be ordered lexicographically ignoring identifiers. The identifier will be used in case of ties.
3. The number– sentence must be put in their original order of occurrence.
Input format :
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first line of each test case contains an integer 'N'.
Then 'N' lines follow.
Each line contains a single string, representing the sentence of the array.
Output format :
For each test case, print 'N' lines.
Then 'N' lines follow.
Each line will contain a single string, representing a sentence of the array in sorted order as mentioned in the description.
Print the output of each test case in a separate line
Constraints :
1 <= T <= 10
0 <= N <= 1000
3 <= |S| <= 100
Where 'T' denotes the number of test cases, 'N' denotes the number of sentences, and |S| denotes the length of sentence, S.
Time Limit: 1 sec
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
In this solution, the idea is to always pick the smallest letter sentence which is currently available in our list/array and add it to the answer. If there is no letter sentence available in the current list/array then add remaining number sentences to answer.
Below is the implementation of the above approach :
- Declare an empty array of strings, say the answer.
- Pick the smallest available letter sentence from a given array of sentences. Let’s called it small.
- Add this small to answer.
- Remove small from the original list.
- Repeat steps 2,3 and 4 until there is no letter sentence left.
- Add remaining number sentences to answer.
- Finally, return the answer.
In this solution, the idea is to sort the sentences using the comparator function.
The comparator function is basically used to define the pairwise relationship. In this case, we will define less than (<) relationship among pairs based on the following criteria :
- All letter – sentences < number – sentence.
- The letter sentences must be sorted in lexicographically order ignoring identifier. The identifier will be used in case of ties.
- The number–sentence must remain in the same order as they are in the given array.
Below is the implementation of the above approach :
- Declare an empty array of strings to store sentences, say the answer.
- Store all letter sentences in one array and number sentences on another array.
- Declare a comparator which will take arguments as pairs lets say pair1 and pair2.
- Ignore identifier of both pair1 and pair2 and store characters of pair1 in content1 and characters of pair2 in content2 of both pairs then following conditions will occur:
- If content1 < content2 then return true.
- If content2 < content1 then return false.
- If content1 = content2 then move to comparison based on the identifier.
- Let’s say identifier of pair1 is id1 and an identifier of pair2 is id2, then if id1 <= id2 then return pair1 as smallest else return pair2 as smallest.
- Call the sort function and pass comparator as an argument to sort letter sentences
- Add letter sentences and digit sentences to answer.
- At last, return answer.