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.

Approach

C++

#include <bits/stdc++.h>
using namespace std;

string sortSentence(string s)
{

    string res = "";
    vector<string> arr(10);

    int n = s.size(), i = 0;
    while (i < n)
    {
        string str = "";
        while (i < n && s[i] == ' ')
            i++;
        while (i < n && s[i] != ' ')
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                arr[s[i] - '0'] = str;
                i++;
                continue;
            }
            str += s[i];
            i++;
        }
    }
    for (int i = 0; i < 10; i++)
    {
        if (arr[i].size() > 0)
        {
            res += arr[i];
            res += " ";
        }
    }
    res.resize(res.size() - 1);
    return res;
}

int main()
{
    string s = "is2 sentence4 This1 a3";

    cout << sortSentence(s) << "\n";

    return 0;
}