We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sorting the Sentence

Difficulty: Easy

Problem Description

Given a shuffled sentence containing no more than 9 words, reconstruct and return the original sentence. Each word in the sentence has been appended with its 1-indexed word position, and the words can be rearranged.

Key Insights

  • Each word in the shuffled sentence ends with a digit indicating its original position.
  • The goal is to sort the words based on these appended digits.
  • After sorting, the numbers can be removed to reconstruct the original sentence.
  • The constraints ensure that the input is manageable in size (no more than 9 words).

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the words. Space Complexity: O(n) - for storing the words in a list.

Solution

To solve the problem, we can follow these steps:

  1. Split the input string into individual words.
  2. Create a list to store the words along with their respective positions.
  3. Sort the list of words based on the extracted numeric positions.
  4. Join the sorted words into a single string, omitting the numeric positions to reconstruct the original sentence.

We will use a list to hold the words and a sorting function to arrange them based on the numeric suffix.

Code Solutions

def sortSentence(s: str) -> str:
    # Split the sentence into words
    words = s.split()
    # Create a list to hold the sorted words
    sorted_words = [''] * len(words)
    
    # Place each word in its correct position
    for word in words:
        position = int(word[-1]) - 1  # Get the position from the last character
        sorted_words[position] = word[:-1]  # Store the word without the number
    
    # Join the sorted words into a single string
    return ' '.join(sorted_words)
← Back to All Questions