Last Updated: 8 Jan, 2022
Sentence Sort
Easy
Asked in companies
You are given a sentence in the form of a string ‘str’ containing no more than 9 words, each word in the sentence is suffixed by a unique number ranging from 1 to N, where N is the number of words in the sentence. Your task is to reorder the words in ‘str’ according to the suffix number of each word and return it as the string.
For Example:
You are given ‘str’ = ‘A1 person3 good2’, in this we can see the ordering of the words like ‘A’, ‘good’ ‘person’ according to the suffix number. Hence the answer string is ‘A good person’.
Input Format:
The first line of input contains a single integer ‘T’, representing the number of test cases.
The first line of each test case contains a string ‘str’ representing the given string.
Output Format:
For each test case, print a single string representing the sorted string.
Print a separate line for each test case.
Constraints:
1 <= T <= 10
1 <= |str| <= 10^6
‘str’ will contain upper and lower case characters of the English alphabet.
‘str’ will not contain more than 9 words.
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 approach, we will separate the words from the sentence and sort them according to the suffix number at the end of the word. We will create an array of pairs with the first element of the pair as the index and the second element as the word. Then after sorting the array we can simply join all the second elements of the pairs in the array to a string and separate them by space.
Algorithm:
- Initialise an empty array wordList
- Split ‘str’ on spaces and iterate word through the resulting list
- Set wordPair as a pair of the last index of word and substring from the first index till the second-last index of word.
- Insert wordPair into wordList
- Sort wordList
- Create an empty string resString
- Iterate through word through wordList and add word[1] to resString
- Return resString