1859. 將句子排序

一個 句子?指的是一個序列的單詞用單個空格連接起來，且開頭和結尾沒有任何空格。每個單詞都只包含小寫或大寫英文字母。

我們可以給一個句子添加 從 1 開始的單詞位置索引 ，并且將句子中所有單詞?打亂順序?。

比方說，句子?“This is a sentence”?可以被打亂順序得到?“sentence4 a3 is2 This1”?或者?“is2 sentence4 This1 a3”?。
給你一個 打亂順序?的句子?s?，它包含的單詞不超過?9?個，請你重新構造并得到原本順序的句子。

示例 1：輸入：s = "is2 sentence4 This1 a3"
輸出："This is a sentence"
解釋：將 s 中的單詞按照初始位置排序，得到 "This1 is2 a3 sentence4" ，然后刪除數字。
示例 2：輸入：s = "Myself2 Me1 I4 and3"
輸出："Me Myself and I"
解釋：將 s 中的單詞按照初始位置排序，得到 "Me1 Myself2 and3 I4" ，然后刪除數字。

提示：

• 2 <= s.length <= 200
• s?只包含小寫和大寫英文字母、空格以及從?1?到?9?的數字。
• s?中單詞數目為?1?到?9?個。
• s?中的單詞由單個空格分隔。
• s?不包含任何前導或者后綴空格。

解題思路

1. 首先我們需要將被打亂順序的所有單詞分離出來，所以先需要使用空格來劃分字符串，如果對于每一個被打亂順序的單詞，末尾都存在一個序號的標記，因此我們使用map，完成序號跟字符串的匹配關系
2. 因為字符串它包含的單詞不超過?9?個，因此序號最多只能為9，因此我們只需要按需要將字符串拼接起來就可以了。

代碼

class Solution {
public:string sortSentence(string s) {map<int,string> m;for (int i = 0; i < s.size(); ++i) {if (s[i]!=' '){int start=i;while (i < s.size()&&s[i]!=' '){i++;}m[s[i-1]-'0']=s.substr(start,i-start-1);}}string res("");for (int i = 1; i <= 9; ++i) {if (m.count(i))res.append(m[i]+" ");else break;}return res.substr(0,res.size()-1);}
};