Code Implementation

class Solution:
    def sortSentence(self, s: str) -> str:
        words = s.split()
        # Create a list of (index, word) tuples
        sorted_words = sorted(words, key=lambda w: int(w[-1]))
        # Remove the trailing digit and join
        return ' '.join(word[:-1] for word in sorted_words)
      

class Solution {
public:
    string sortSentence(string s) {
        vector<string> words;
        stringstream ss(s);
        string word;
        while (ss >> word) {
            words.push_back(word);
        }
        vector<string> res(words.size());
        for (const auto& w : words) {
            int idx = w.back() - '1';
            res[idx] = w.substr(0, w.size() - 1);
        }
        string ans;
        for (int i = 0; i < res.size(); ++i) {
            if (i > 0) ans += " ";
            ans += res[i];
        }
        return ans;
    }
};
      

class Solution {
    public String sortSentence(String s) {
        String[] words = s.split(" ");
        String[] res = new String[words.length];
        for (String word : words) {
            int idx = word.charAt(word.length() - 1) - '1';
            res[idx] = word.substring(0, word.length() - 1);
        }
        return String.join(" ", res);
    }
}
      

var sortSentence = function(s) {
    let words = s.split(' ');
    let res = Array(words.length);
    for (let word of words) {
        let idx = parseInt(word[word.length - 1]) - 1;
        res[idx] = word.slice(0, -1);
    }
    return res.join(' ');
};
      

Problem Description

Given a shuffled sentence s containing words, where each word has a single digit at its end representing its position in the original sentence, your task is to reconstruct the sentence in the correct order. The digits range from 1 to the number of words, and every word includes exactly one such digit at the end. You must return the sentence with words in the correct order, separated by single spaces, and without the digits.

Constraints:

• Each word contains only English letters followed by a single digit.
• The input sentence contains no leading or trailing spaces.
• There is exactly one valid solution.
• Do not reuse or omit any words.

Thought Process

The problem essentially asks us to reorder a list of words based on a numeric suffix. At first glance, a brute-force approach might involve repeatedly searching for the next word in order, but this would be inefficient. Instead, we should take advantage of the fact that each word ends with a unique position digit, and the number of words is known and small.

The key realization is that by extracting the digit from each word, we can directly place the word (minus the digit) into its correct position in a new array or list. This shifts the problem from searching and sorting to a simple mapping based on indices, which is much faster and easier to implement.

Solution Approach

Let's break down the solution into clear steps:

1. Split the input sentence:
   • Use the split() function to divide the sentence into individual words.
2. Map words to positions:
   • For each word, extract the last character (the digit) and convert it to an integer. This gives the intended position (index) for the word.
   • Store each word (without the digit) at its correct index in a result array or list.
3. Construct the final sentence:
   • Join all words in the result array with spaces to form the correct sentence.

This approach is efficient because it processes each word only once and uses direct indexing for placement.

Example Walkthrough

Example Input: "is2 sentence4 This1 a3"

1. Split: The words are ["is2", "sentence4", "This1", "a3"]
2. Process each word:
   • "is2": The digit is 2, so "is" goes to position 2 (index 1)
   • "sentence4": The digit is 4, so "sentence" goes to position 4 (index 3)
   • "This1": The digit is 1, so "This" goes to position 1 (index 0)
   • "a3": The digit is 3, so "a" goes to position 3 (index 2)
3. Result array: ["This", "is", "a", "sentence"]
4. Join and return: "This is a sentence"

Each word is placed directly at its corresponding index, making the reconstruction straightforward and efficient.

Time and Space Complexity

Brute-force approach:

• If you searched for each index by scanning the list each time, it would be O(n^2), where n is the number of words.

• Splitting the sentence and processing each word is O(n).
• Constructing the result array and joining the words is also O(n).
• Total time complexity: O(n)
• Space complexity: O(n) for the result array.

The optimized solution is linear in both time and space because each word is handled exactly once and stored in a new list.

Summary

The problem leverages unique numeric suffixes to efficiently reconstruct the original sentence. By mapping each word to its intended position using the digit, we avoid unnecessary searching or sorting. The solution is both simple and optimal, requiring only a single traversal and direct placement, which makes it a great example of using indexing and mapping to solve ordering problems efficiently.