1859. Sorting the Sentence
Problem Description
In this problem, we are given a sentence that has been jumbled in a particular way. Initially, the sentence was a list of words separated by spaces with no leading or trailing spaces. However, it has been 'shuffled' by appending a 1-indexed position number at the end of each word, and then the words have been rearranged. Our goal is to reconstruct the original sentence from this shuffled version.
For example, the original sentence "I have a cat" could be converted to "I1 have2 a4 cat3" in its shuffled form, and we would need to rearrange it back to the original order.
The constraints tell us that the shuffled sentence will contain no more than 9 words, and each word consists only of lowercase or uppercase English letters followed by the position number.
Intuition
The solution involves taking the following steps:
- Split the shuffled sentence into individual words, so we can process each word separately.
- Each word ends with a digit that indicates its original position in the sentence before shuffling. We need to create a structure, like a list, to hold the words in their correct positions.
- Loop over each word from the shuffled sentence. Extract the last character of each word, which is the digit. Since we know that the position number is 1-indexed and Python lists are 0-indexed, we subtract 1 from the extracted digit to find the correct index for placing the word in our list.
- Remove the digit from each word as we place the word into the correct position in our list.
- Once all words are placed in their correct positions, we join them back into a sentence using a space as the separator.
The rationale for this approach is that we can use the position numbers as indices for an array or a list. By doing so, we ensure that each word is placed exactly in the position it was before shuffling. Since the words can only be shuffled by their positional indices and the indices are unique, this method guarantees that we can recover the original sentence.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution uses Python's built-in string and list operations to deconstruct and reconstruct the sentence. Here are the steps following the algorithm:
-
String Splitting: The given shuffled sentence
s
is split using thesplit()
method, which divides the sentence into a list of words based on spaces.1words = s.split()
-
List Initialization: A new list
ans
is created with the same length as the number of words. Each element is initialized asNone
to be filled in with the corresponding sorted word.1ans = [None] * len(words)
-
Loop and Parsing: Each word in the list
words
is processed in a loop.1for w in words:
For each word
w
, the last character (which is a digit representing the word's original position) is converted to an integer and 1 is subtracted to account for Python's 0-based indexing.1i = int(w[-1]) - 1
Then the digit is removed from the word, and the resulting word (with the digit removed) is placed at the correct index in
ans
.1ans[i] = w[:-1]
-
Joining the List: Finally, the list
ans
is joined into a string using' '.join(ans)
with spaces between elements to form the reconstructed sentence.1return ' '.join(ans)
In terms of data structures, a list is used to hold the words at the indices corresponding to their original positions. This means we make use of the array index as a direct access table.
In terms of patterns, the solution utilizes simple parsing of strings and the strategy of using an auxiliary data structure (list) to organize items based on specific keys (in this case, the number appended to each word). The algorithm complexity is O(n) where n is the number of words in the sentence, as each word is visited exactly once to place it in its correct position.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to illustrate the solution approach. Suppose the shuffled sentence given is "is2 This1 an4 example3"
. Our goal is to rearrange it back to "This is an example"
.
Here is how the algorithm works:
-
String Splitting: We first split the shuffled sentence into words:
1words = "is2 This1 an4 example3".split() # words = ['is2', 'This1', 'an4', 'example3']
-
List Initialization: We prepare a new list with the length equal to the number of words, which is 4 in our example:
1ans = [None] * len(words) # ans = [None, None, None, None]
-
Loop and Parsing: We then loop through each word in our list of words and parse each one.
1for w in words: 2 i = int(w[-1]) - 1 # For 'is2', i = 2 - 1 = 1 3 ans[i] = w[:-1] # The word without the last character ('is') is placed in 'ans' at index 1
Following this step for each word places them in their correct positions on the
ans
list:'This1'
goes toans[0]
'is2'
goes toans[1]
'example3'
goes toans[2]
'an4'
goes toans[3]
Now our
ans
list looks like this:['This', 'is', 'example', 'an']
-
Joining the List: The last step is to join these words with spaces to form the reconstructed sentence:
1return ' '.join(ans) # "This is example an"
However, we notice that the output doesn't quite match the expected sentence "This is an example"
. Upon reviewing the loop, we realize that we have incorrectly sequenced 'example'
and 'an'
due to a mistake in their indices. Correctly placing 'an'
in ans[2]
and 'example'
in ans[3]
during the parsing loop we get the right order:
'This1'
goes toans[0]
'is2'
goes toans[1]
'an4'
goes toans[2]
'example3'
goes toans[3]
Now ans
is ['This', 'is', 'an', 'example']
, and after joining, it indeed forms the correct original sentence "This is an example"
.
Solution Implementation
1class Solution:
2 def sortSentence(self, sentence: str) -> str:
3 # Split the sentence into a list of words
4 words = sentence.split()
5
6 # Initialize a list with the same length as the number of words
7 sorted_words = [None] * len(words)
8
9 # Iterate over each word in the list
10 for word in words:
11 # The index is the last character of the word, converted to an integer and decremented by 1
12 index = int(word[-1]) - 1
13 # Assign the word (without the last character) to the correct position
14 sorted_words[index] = word[:-1]
15
16 # Join the list of words into a sentence with spaces between words
17 return ' '.join(sorted_words)
18
1class Solution {
2 public String sortSentence(String s) {
3 // Split the input string into words based on spaces
4 String[] words = s.split(" ");
5
6 // Create an array to hold the sorted words
7 String[] sortedWords = new String[words.length];
8
9 // Iterate over the array of words
10 for (String word : words) {
11 // Find the index for the sorted position from the last character of the word
12 // '1' is subtracted because the positions in the task are 1-based and array indices are 0-based
13 int index = word.charAt(word.length() - 1) - '1';
14
15 // Assign the word without the number to the correct position in the sortedWords array
16 // The substring method excludes the last character which is the digit
17 sortedWords[index] = word.substring(0, word.length() - 1);
18 }
19
20 // Join the sorted words into a single string with spaces and return it
21 return String.join(" ", sortedWords);
22 }
23}
24
1#include <string>
2#include <sstream>
3#include <vector>
4
5class Solution {
6public:
7 // The function takes a scrambled sentence with words followed by their position
8 // in the original sentence and returns the sorted sentence.
9 string sortSentence(string s) {
10 istringstream iss(s); // Used to split the string into words based on whitespace
11 string word; // Temporary string to hold each word from the stream
12 vector<string> words; // To store words as they are read from the stream
13
14 // Reading words from the stringstream into the vector
15 while (iss >> word) {
16 words.push_back(word);
17 }
18
19 // Create a result vector with the same size as the number of words
20 vector<string> result(words.size());
21
22 // Placing words at their correct index as indicated by the last character
23 for (auto& currWord : words) {
24 // Find the index by subtracting '1' to convert char to int (0-based indexing)
25 int index = currWord.back() - '1';
26 // Add the word to the result without the number
27 result[index] = currWord.substr(0, currWord.size() - 1);
28 }
29
30 // Construct the sorted sentence by concatenating words in the result
31 string sortedSentence; // To store the final sorted sentence
32 for (auto& sortedWord : result) {
33 sortedSentence += sortedWord + " "; // Add each word followed by a space
34 }
35
36 // Remove the trailing space from the last word
37 sortedSentence.pop_back();
38
39 // Return the sorted sentence
40 return sortedSentence;
41 }
42};
43
1// This function sorts a sentence based on the numerical indices attached to its words.
2function sortSentence(sentence: string): string {
3 // Split the sentence into words based on space delimiter.
4 const words = sentence.split(' ');
5
6 // Initialize an array to hold the sorted words. Its length is the same as the number of words.
7 const sortedWords = new Array<string>(words.length);
8
9 // Iterate over each word to place them in the correct position.
10 for (const word of words) {
11 // The index for the word's position is at the end of the word (one digit).
12 // Subtract the char code of '1' to convert from char to actual numerical index.
13 const index = word.charCodeAt(word.length - 1) - '1'.charCodeAt(0);
14
15 // Assign the word (without the numerical index) to the correct position.
16 sortedWords[index] = word.slice(0, -1); // Slice off the last character, the numerical index.
17 }
18
19 // Join the sorted words back into a sentence with spaces and return the sorted sentence.
20 return sortedWords.join(' ');
21}
22
Time and Space Complexity
Time Complexity
The time complexity of the given sortSentence
function can be analyzed as follows:
- Splitting the sentence into words with
s.split()
. In the worst case, this operation has a time complexity ofO(n)
, wheren
is the length of the input strings
. - Initializing the answer list
ans
withNone
* the number of words. The time complexity of this operation isO(m)
, wherem
is the number of words ins
. - Looping over each word
w
to place it at the correct position inans
. This is anotherO(m)
operation, as it iterates through all words once. - Within the loop, extracting the position
i
and word without the numberw[:-1]
isO(1)
for each word since the word is sliced at a constant index from the end and assigning the position is a direct index access. - Joining the words in
ans
into a single string with' '.join(ans)
. The time complexity of this operation can be seen asO(m * k)
, wherek
is the average length of a word without the trailing number, as it has to concatenate each word with a space in between.
The dominant factors are the splitting of the initial string and the joining of the words in the list. Therefore, the total time complexity is O(n + m + m * k)
, which can be simplified to O(n + m * k)
because both n
and k
are related to the length of the input string s
.
Space Complexity
The space complexity of the sortSentence
function can be analyzed as follows:
- The list of words obtained from splitting the string
s.split()
requiresO(m)
space, wherem
is the number of words. - The
ans
list also requiresO(m)
space to hold the words in their sorted order. - Temporary variables such as
w
andi
use a constantO(1)
space as they are just references to elements in the list or integers.
Hence, the total space complexity is O(m) + O(m)
which equals O(m)
, where m
is the number of words in the sentence.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.