{x}
blog image

Sorting the Sentence

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.

  • For example, 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 <= 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 Explanation: Sorting the Sentence

This problem requires reconstructing a sentence from a shuffled string where each word has its position appended. The solution leverages the position information to sort the words back into their original order.

Approach:

The most efficient approach involves using the word's trailing digit (its position) as an index into a new array. This allows for direct placement of the word in its correct location, avoiding the need for full sorting algorithms like merge sort or quicksort which would have a higher time complexity.

Algorithm:

  1. Split the string: The input string s is split into an array of words (ws) using space as a delimiter.

  2. Create a result array: An array ans of the same size as ws is created to store the words in their correct order. This array is initialized with null or equivalent to indicate empty slots.

  3. Iterate and place: The code iterates through each word in ws. For each word:

    • The last character is extracted (this is the word's position).
    • The last character is converted to an integer (subtracting the ASCII value of '1' to get a 0-based index).
    • The word (without the trailing digit) is placed at the calculated index in the ans array.

  4. Join and return: Finally, the elements of the ans array (now containing the words in correct order) are joined together with spaces to form the reconstructed sentence, which is then returned.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the input string. This is because we iterate through the words once to extract positions and place them in the result array, and then iterate again to join the words. The splitting and joining operations also take linear time.

  • Space Complexity: O(n). This is due to the creation of the ws array (to store split words) and the ans array (to store the result), both of which have a size proportional to the number of words in the sentence.

Code Examples (with explanations):

The code examples provided in the previous response demonstrate the algorithm in several programming languages. Let's examine the Python3 example in detail:

class Solution:
    def sortSentence(self, s: str) -> str:
        ws = s.split()  # Split the string into a list of words
        ans = [None] * len(ws)  # Create a result array of the same size, initialized with None
        for w in ws:
            index = int(w[-1]) - 1  # Extract the last character (position), convert to integer, and adjust to 0-based index
            ans[index] = w[:-1]  # Place the word (without the trailing digit) at the calculated index
        return " ".join(ans)  # Join the words in the result array with spaces

Each language's implementation follows the same core logic, differing only in syntax and specific function calls for string manipulation (splitting, joining, substring extraction). The other code examples (Java, C++, Go, TypeScript, JavaScript) demonstrate the adaptability of the algorithm across different languages. They all maintain the linear time and space complexity.