Sentence Sort

Easy
0/40
profile
Contributed by
11 upvotes
Asked in companies
AmazonGoogle inc

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
A1 person3 good2
world2 hello1
Sample Input 2:
A good person
hello world
Explanation for input 1:
For the first test case, ‘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’.

For the second test case, ‘str’ = ‘world2 hello1’, in this we can see the ordering of the words like ‘ hello’, and ‘world’, according to the suffix number Hence the answer string is ‘hello world’.
Sample Input 2:
2
Code1 studio2 coding3 ninjas4
hi1
Sample Output 2:
Code studio coding ninjas
hi
Hint

Try to separate the words and sort them according to the index

Approaches (1)
Sorting With Index

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
Time Complexity

O(N), Where N is the length of the given string.

 

We are iterating over the string which will cost O(N) time. Sorting the list of words will also take O(N) as there can be a maximum of 9 elements in the array. Hence the overall time complexity is O(N).

Space Complexity

O(N), Where N is the length of the given string.
 

We are maintaining an array of word pairs that will take O(N) space. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Sentence Sort
Full screen
Console