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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sorting the Sentence

Number: 1970

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

A sentence is a list of words separated by a single space, where each word has an appended digit representing its original position. Given such a shuffled sentence, the goal is to rearrange the words in their correct order and then remove the digits, returning the restored sentence.

Key Insights

  • Each word ends with a digit indicating its position.
  • The sentence can be split into individual words.
  • Sorting the list of words using the digit (last character) as the key reorders them to their original positions.
  • Once sorted, removing the trailing digit from each word yields the final sentence.

Space and Time Complexity

Time Complexity: O(n log(n)) due to sorting the words, though n is at most 9. Space Complexity: O(n) to store the split words.

Solution

The approach is straightforward:

  1. Split the sentence into words by spaces.
  2. Sort the words by converting the last character (which is a digit) to an integer and using it as the key.
  3. Remove the last character (digit) from each word after sorting.
  4. Join the modified words with spaces to form the original sentence.

Key data structures used: array (or list) to store the words, and built-in sort functions available in most languages.

Code Solutions

def sort_sentence(s):
    # Split the sentence into individual words
    words = s.split(" ")
    # Sort the words based on the trailing digit, using int conversion for accurate numeric comparisons
    sorted_words = sorted(words, key=lambda word: int(word[-1]))
    # Remove the trailing digit from each word and join them to form the final sentence
    return " ".join(word[:-1] for word in sorted_words)

# Example usage:
if __name__ == "__main__":
    example = "is2 sentence4 This1 a3"
    print(sort_sentence(example))  # Expected output: "This is a sentence"
← Back to All Questions