Sorting the Sentence
Problem
Given a shuffled sentence whose words end with their original 1-indexed position, reconstruct it.
s = "is2 sentence4 This1 a3""This is a sentence"def sort_sentence(s):
words = s.split()
out = [''] * len(words)
for w in words:
out[int(w[-1]) - 1] = w[:-1]
return ' '.join(out)function sortSentence(s) {
const words = s.split(' ');
const out = new Array(words.length);
for (const w of words) {
out[Number(w[w.length - 1]) - 1] = w.slice(0, -1);
}
return out.join(' ');
}class Solution {
public String sortSentence(String s) {
String[] words = s.split(" ");
String[] out = new String[words.length];
for (String w : words) {
int p = w.charAt(w.length() - 1) - '0';
out[p - 1] = w.substring(0, w.length() - 1);
}
return String.join(" ", out);
}
}string sortSentence(string s) {
vector<string> words;
stringstream ss(s); string w;
while (ss >> w) words.push_back(w);
vector<string> out(words.size());
for (auto& x : words) {
int p = x.back() - '0';
out[p - 1] = x.substr(0, x.size() - 1);
}
string result;
for (size_t i = 0; i < out.size(); i++) { if (i) result += ' '; result += out[i]; }
return result;
}Explanation
Each shuffled word carries its own correct position as a digit at the end. So instead of sorting, we can just place every word directly into its final slot using that digit.
We split the sentence into words, then make an output list out sized to the number of words. For each word w, the last character w[-1] is its 1-indexed position, so we drop the rest of the word, w[:-1], into out[int(w[-1]) - 1] (subtracting 1 because list indexes start at 0).
Because every word tells us exactly where it belongs, the order we read them in doesn't matter — they each land in the right spot. Finally we join out with single spaces.
Example: s = "is2 sentence4 This1 a3". This1 goes to slot 0, is2 to slot 1, a3 to slot 2, sentence4 to slot 3. Joining gives "This is a sentence".
This is a single pass that buckets each word by its index, so it's fast and avoids any actual sorting comparisons.