Sorting the Sentence

Difficulty: Easy | Acceptance: 84.10% | Paid: No Topics: String, Sorting

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.

Convert the sentence to a sentence where the words are sorted in ascending order based on the digit at the end of each word.

The digit at the end of a word represents its position in the sorted sentence (1-indexed).

Remove the digit from the end of each word and return the reconstructed sentence.

• Examples
• Constraints
• Approach 1: Sorting
• Approach 2: Bucket Sort (Array Placement)

Examples

Example 1:

Input: s = "is2 sentence4 This1 a3"
Output: "This is a sentence"
Explanation: Sort the words by the number at the end:
"This1" -> "This"
"is2" -> "is"
"a3" -> "a"
"sentence4" -> "sentence"
Join them with a space to get "This is a sentence".

Example 2:

Input: s = "Myself2 Me1 I4 and3"
Output: "Me Myself and I"
Explanation: Sort the words by the number at the end:
"Me1" -> "Me"
"Myself2" -> "Myself"
"and3" -> "and"
"I4" -> "I"
Join them with a space to get "Me Myself and I".

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.
s does not contain leading or trailing spaces.
All words are separated by a single space.

Approach 1: Sorting

Intuition We can split the sentence into individual words. Since the last character of each word is its target index, we can sort the array of words based on this character. Finally, we strip the trailing digit from each word and join them back together.

Steps

• Split the input string s by spaces to get an array of words.
• Sort the array using a custom comparator that compares the last character of each word.
• Iterate through the sorted array, removing the last character from each word.
• Join the processed words with a space and return the result.

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split()
        words.sort(key=lambda x: x[-1])
        return ' '.join(w[:-1] for w in words)

Complexity

• Time: O(N log N) due to sorting, where N is the number of words.
• Space: O(N) to store the array of words.
• Notes: Simple and readable, leveraging built-in sort functions.

Approach 2: Bucket Sort (Array Placement)

Intuition Since the digits at the end of the words are unique and range from 1 to 9, we can use a bucket sort approach. We create an array (or list) of size equal to the number of words and place each word directly into its correct position based on the trailing digit. This avoids the O(N log N) sorting step.

Steps

• Split the input string s by spaces to get an array of words.
• Initialize a result array of strings with the same length as the words array.
• Iterate through the words. For each word, extract the last character to determine the index (convert char to int, subtract 1).
• Place the word (without the last character) into the result array at the calculated index.
• Join the result array with spaces and return.

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split()
        res = [''] * len(words)
        for w in words:
            idx = int(w[-1]) - 1
            res[idx] = w[:-1]
        return ' '.join(res)

Complexity

• Time: O(N), where N is the number of words. We iterate through the words once to place them.
• Space: O(N) to store the result array.
• Notes: More efficient than sorting as it runs in linear time relative to the number of words.