Sorting the Sentence — Solution in Python, Java & C++
Sorting the Sentence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sorting the Sentence is an easy coding problem on strings and sorting, asked in Amazon and Zoho interviews.
- Difficulty: Easy
- Topics: Strings, Sorting
- Asked at: Amazon, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sentence was shuffled by appending the 1-indexed position of each word to the end of that word, then rearranging the words.
Given such a shuffled sentence s, reconstruct and return the original sentence.
Example 1
Input: s = "is2 sentence4 This1 a3"
Output: This is a sentence
Example 2
Input: s = "Myself2 Me1 I4 and3"
Output: Me Myself and I
Example 3
Input: s = "there1"
Output: there
Constraints
2 <= s.length <= 60Each word ends in a single digit giving its position.There are at most 9 words.
Hints for Sorting the Sentence
Hint 1
The last character of each word is its destination, 1-indexed.
Hint 2
Strip that digit off and write the remaining word straight into its slot.
Hint 3
Then join the slots with single spaces.
How to solve Sorting the Sentence
Each word's last character is its 1-based destination; strip it and drop the word into that slot.
Approach
- Split on spaces.
- For each word, write
word[:-1]intoout[int(word[-1]) - 1]. - Join the slots with a space.
Why it works
The position suffix is a permutation of 1..n, so every slot is filled once and the join restores the original order.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- At most 9 words, so the suffix is a single digit — parsing
word[-1]is enough.
Reference solution
Python
def sortSentence(s: str) -> str:
parts = s.split(" ")
out = [""] * len(parts)
for word in parts:
out[int(word[-1]) - 1] = word[:-1]
return " ".join(out)Java
public static String sortSentence(String s) {
String[] pieces = s.split(" ");
String[] out = new String[pieces.length];
for (String w : pieces) {
int pos = w.charAt(w.length() - 1) - '0';
out[pos - 1] = w.substring(0, w.length() - 1);
}
return String.join(" ", out);
}C++
string sortSentence(string s) {
vector<string> pieces;
string cur = "";
for (char c : s) {
if (c == ' ') { pieces.push_back(cur); cur = ""; }
else cur += c;
}
pieces.push_back(cur);
vector<string> out(pieces.size());
for (string& w : pieces) {
int pos = w[w.size() - 1] - '0';
out[pos - 1] = w.substr(0, w.size() - 1);
}
string result = "";
for (size_t i = 0; i < out.size(); i++) {
if (i > 0) result += " ";
result += out[i];
}
return result;
}JavaScript
var sortSentence = function(s) {
const parts = s.split(" ");
const out = new Array(parts.length).fill("");
for (let i = 0; i < parts.length; i++) {
const w = parts[i];
const pos = parseInt(w[w.length - 1], 10);
out[pos - 1] = w.slice(0, w.length - 1);
}
return out.join(" ");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sorting Algorithms