#1859

Easy

LeetCode Problem Workspace

Sorting the Sentence

Reconstruct a shuffled sentence by sorting words using their embedded indices to restore the original sentence order efficiently.

string sorting

Problem Statement

You are given a shuffled sentence s where each word has a numeric suffix representing its 1-indexed original position. Words are separated by a single space with no leading or trailing spaces, and each word contains only English letters followed by a single digit.

Your task is to reorder the words according to their numeric suffixes and return the reconstructed sentence as a string without the numeric indices. The input contains at most 9 words, and the solution should handle typical string parsing and sorting efficiently.

Examples

Example 1

Input: s = "is2 sentence4 This1 a3"

Output: "This is a sentence"

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"

Sort the words in s to their original positions "Me1 Myself2 and3 I4", then remove the numbers.

Constraints

2 <= s.length <= 200
s consists of lowercase and uppercase English letters, spaces, and digits from 1 to 9.
The number of words in s is between 1 and 9.
The words in s are separated by a single space.
s contains no leading or trailing spaces.

Solution Approach

Extract positions and words

Split the input string by spaces into individual words. For each word, separate the numeric suffix to determine its original index and store both the word without the number and its index for sorting.

Sort words based on indices

Use a sorting algorithm or array placement to reorder words according to their extracted numeric indices. Ensure stability so words with unique positions appear in their correct places.

Reconstruct and return sentence

Join the sorted words back into a single string separated by spaces, removing the numeric suffixes, to produce the original sentence order as the final output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for parsing and O(n log n) if sorting by indices, but since n <= 9, the practical runtime is constant. Space complexity is O(n) for storing words and their positions.

What Interviewers Usually Probe

Check if the candidate efficiently extracts numeric indices from words without extra string manipulations.
Watch for correct placement of words in their original positions, especially when input is already partially ordered.
Confirm candidate handles edge cases with minimum or maximum number of words correctly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to remove the numeric suffix after sorting, resulting in incorrect output.
Using unstable sorting which can mix up words with similar numeric positions.
Incorrectly parsing the string, especially splitting or indexing errors on words.

Follow-up variants

Reconstruct sentences with multi-digit indices requiring robust parsing logic.
Handle shuffled sentences with punctuation attached to words, needing clean separation before sorting.
Optimize in-place sorting using index mapping instead of extra arrays for space efficiency.

FAQ

What is the main approach for Sorting the Sentence on LeetCode?

Split words, extract numeric positions, sort or place them according to indices, and remove numbers to rebuild the sentence.

Can this problem be solved without explicit sorting?

Yes, since the number of words is limited, you can directly place each word in a pre-sized array at its index.

How do I handle single-word or two-word sentences?

Even with minimal words, apply the same extraction and placement logic; the solution naturally handles small cases.

Are there any edge cases for index numbers?

Indices are 1-based and at most 9, so verify parsing extracts digits correctly without assuming multi-digit numbers.

Does the Sorting plus String pattern generalize to other problems?

Yes, this pattern of extracting keys from strings and ordering elements is common for similar string sorting tasks.

terminal

Solution

Solution 1: String Splitting

First, we split the string $s$ by spaces to get the array of strings $\textit{ws}$. Then, we iterate through the array $\textit{ws}$, subtracting the character '1' from the last character of each word to get the result as the index of the word. We take the prefix of the word as the content of the word. Finally, we concatenate the words in index order.

1

2

3

4

5

6

7

class Solution:
    def sortSentence(self, s: str) -> str:
        ws = s.split()
        ans = [None] * len(ws)
        for w in ws:
            ans[int(w[-1]) - 1] = w[:-1]
        return " ".join(ans)

Continue Practicing

#1985 find the kth largest integer in the array #1657 determine if two strings are close #1647 minimum deletions to make character frequencies unique