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 the split() method, which divides the sentence into a list of words based on spaces.
```
words = s.split()
```
List Initialization: A new list ans is created with the same length as the number of words. Each element is initialized as None to be filled in with the corresponding sorted word.
```
ans = [None] * len(words)
```
Loop and Parsing: Each word in the list words is processed in a loop.
```
for 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.
```
i = 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.
```
ans[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.
```
return ' '.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 Evaluator

Example 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:

words = "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:

ans = [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.

for w in words:
    i = int(w[-1]) - 1  # For 'is2', i = 2 - 1 = 1
    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 to ans[0]
'is2' goes to ans[1]
'example3' goes to ans[2]
'an4' goes to ans[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:

return ' '.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 to ans[0]
'is2' goes to ans[1]
'an4' goes to ans[2]
'example3' goes to ans[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 of O(n), where n is the length of the input string s.
Initializing the answer list ans with None * the number of words. The time complexity of this operation is O(m), where m is the number of words in s.
Looping over each word w to place it at the correct position in ans. This is another O(m) operation, as it iterates through all words once.
Within the loop, extracting the position i and word without the number w[:-1] is O(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 as O(m * k), where k 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() requires O(m) space, where m is the number of words.
The ans list also requires O(m) space to hold the words in their sorted order.
Temporary variables such as w and i use a constant O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know