Watch 10 video solutions for Sorting the Sentence, a easy level problem involving String, Sorting. This walkthrough by Code with Alisha has 14,045 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each word consists of lowercase and uppercase English letters.
A sentence can be shuffled by appending the 1-indexed word position to each word then rearranging the words in the sentence.
"This is a sentence" can be shuffled as "sentence4 a3 is2 This1" or "is2 sentence4 This1 a3".Given a shuffled sentence s containing no more than 9 words, reconstruct and return the original sentence.
Example 1:
Input: s = "is2 sentence4 This1 a3" Output: "This is a sentence" Explanation: Sort the words in s to their original positions "This1 is2 a3 sentence4", then remove the numbers.
Example 2:
Input: s = "Myself2 Me1 I4 and3" Output: "Me Myself and I" Explanation: Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.
Constraints:
2 <= s.length <= 200s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.s is between 1 and 9.s are separated by a single space.s contains no leading or trailing spaces.Problem Overview: You receive a shuffled sentence where each word ends with a digit representing its correct position in the sentence. Your task is to reorder the words based on these indices and return the original sentence without the digits.
The input looks like "is2 sentence4 This1 a3". Each word contains its position at the end. The goal is to place every word in its correct position and remove the trailing number.
Approach 1: Sorting + String Manipulation (O(n log n) time, O(n) space)
Split the sentence into words using whitespace. Each word contains its index as the last character, so you can extract that digit and use it as the sorting key. After sorting the array of words by their index, remove the trailing digit from each word and join them back into a sentence. This approach relies on built‑in sorting from the sorting category and basic string operations. The implementation is straightforward and readable, but the sort operation introduces O(n log n) time complexity.
Approach 2: Array Indexing (O(n) time, O(n) space)
The index digit at the end of each word already tells you the exact final position. Instead of sorting, create an array of size n where n is the number of words. Iterate through each word, extract the index, remove the digit, and place the word directly at result[index - 1]. After processing all words, join the array into the final sentence. This method avoids sorting completely and processes each word exactly once, achieving O(n) time. The approach uses simple array placement and string slicing.
The key insight is that the index digit encodes the final position explicitly. Sorting works because the digit defines order, but direct indexing is faster because it skips the comparison step entirely.
Recommended for interviews: Interviewers typically expect the linear-time array indexing solution. It demonstrates that you noticed the positional information embedded in each word and used it to avoid sorting. Showing the sorting approach first proves you understand the problem quickly, but implementing the O(n) direct placement solution shows stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + String Manipulation | O(n log n) | O(n) | Quick and readable solution using built-in sorting |
| Array Indexing (Direct Placement) | O(n) | O(n) | Optimal approach when positions are encoded in the data |