185. Sorting the Sentence

A sentence is a list of words separated by spaces with no leading or trailing spaces.

Each word consists of lowercase and uppercase letters only.

You are given a shuffled sentence where each word has a digit (1–9) appended indicating its original position.

Reconstruct and return the original sentence.

Input: A string where each word ends with its 1-indexed position digit.

Output: The reconstructed original sentence with words in their correct order.

Examples

Input: is2 summer3 Ilove1
Output: Ilove summer is
Explanation: 1→'Ilove', 2→'is', 3→'summer' → 'Ilove is summer'? No: strip digits: Ilove(pos1), is(pos2), summer(pos3) → 'Ilove is summer'.

Input: Me1 know2 soul3
Output: Me know soul
Explanation: Positions 1,2,3 → 'Me know soul'.

Input: hello1
Output: hello
Explanation: Single word at position 1.

Constraints

• 2 <= sentence.length <= 200
• sentence[i] consists of lowercase/uppercase letters and exactly one trailing digit (1-9)
• All position digits are unique and form 1..n

Asked by