5742. 将句子排序

末蓝、 2023-01-21 11:30 11阅读 0赞

# [5742. 将句子排序][5742.] #

一个 **句子** 指的是一个序列的单词用单个空格连接起来，且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。

我们可以给一个句子添加 **从 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` 不包含任何前导或者后缀空格。

# 思路与代码 #

## 某菜的思路(c++语言) ##

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <string>
    #include <unordered_map>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    
    
    using namespace std;
    
    class Solution { 
    private:
    	//参考http://www.cplusplus.com/reference/string/string/c_str/
    	vector<string> split(string& str) { 
    		vector<string> vec;
    		char* cstr = new char[str.length() + 1];
    		strcpy(cstr, str.c_str());
    
    		// cstr now contains a c-string copy of str
    
    		char* p = strtok(cstr, " ");
    		while (p != 0)
    		{ 
    			vec.push_back(p);
    			//std::cout << p << '\n';
    			p = strtok(NULL, " ");
    		}
    
    		delete[] cstr;
    		return vec;
    	}
    public:
    	//方法一：
    	//1.根据空白分割为vector
    	//2.遍历vector得到 单词、下标,保存到map
    	//3.遍历map,将字符串连接起来
    	string sortSentence(string str) { 
    		vector<string> vec = split(str);
    		unordered_map<int, string> mmap;
    		for (auto& it : vec) { 
    			//cout << "it = "<<it << endl;
    			string ss = it;
    			//cout << "index = "<<ss[ss.size() - 1] << endl;
    			//cout << "index = " << ss.substr(ss.size()-1) << endl;
    			int key = atoi(ss.substr(ss.size() - 1).c_str());
    			string value = ss.substr(0, ss.size() - 1);
    			//cout <<"value = "<< value << endl;
    			mmap.insert(pair<int, string>(key, value));
    		}
    		string ans = "";
    		for (size_t i = 0; i < vec.size(); i++)
    		{ 
    			ans += mmap.at(i+1)+" ";
    		}
    		ans = ans.substr(0, ans.size() - 1);
    		return ans;
    	}
    	//方法二：
        //大牛的思路
    	string sortSentence2(string s)
    	{ 
    		vector<pair<int, string>> id_word;
    		for (int i = 0; i < s.size(); i++)
    		{ 
    			int j = i;
    			string word;
    			while (j < s.size() && s[j] != ' ')
    				word += s[j++];
    			i = j;
    			cout << "index = " << word.back() - '0' << endl;
    			id_word.push_back({  word.back() - '0', word.substr(0, word.size() - 1) });
    		}
    
    		sort(id_word.begin(), id_word.end());
    		string res = "";
    		for (auto [i, w] : id_word)
    		{ 
    			res += w;
    			res += ' ';
    		}
    		res.pop_back();
    		return res;
    
    	}
    };
    
    int main()
    { 
    	string str = "is2 sentence4 This1 a3";
    	Solution s;
    	//cout << s.sortSentence(str) << endl;
    	cout << s.sortSentence2(str) << endl;
    }
    
    //输出
    //index = 2
    //index = 4
    //index = 1
    //index = 3
    //This is a sentence

## 大牛的思路(c++语言) ##

上面某菜的代码也包含了这段

class Solution 
    { 
    public:
        string sortSentence(string s) 
        { 
            vector<pair<int, string>> id_word;
            for (int i = 0; i <  s.size();  i ++)
            { 
                int j = i;
                string word;
                while (j < s.size() && s[j] != ' ')
                    word += s[j++];
                i = j;
                id_word.push_back({ word.back() - '0', word.substr(0, word.size() - 1)});
            }
            
            sort(id_word.begin(), id_word.end());
            string res = "";
            for (auto [i, w] : id_word)
            { 
                res += w;
                res += ' ';
            }
            res.pop_back();
            return res;
    
        }
    };
    
    //作者：Hanxin_Hanxin
    //链接：sorting-the-sentence/solution/cpython3-mo-ni-by-hanxin_hanxin-a1or/

## 大牛的python3 ##

class Solution:
        def sortSentence(self, s: str) -> str:
            a = list(s.split()) //这里直接 a = s.split()也是可以的
            dic = dict()
            for word in a:
                w = word[:-1]
                ID = int(word[-1])
                dic[ID] = w
        
            res = []
            tmp = list(dic.items()) 
            tmp.sort(key = lambda x: x[0])
            for i, w in tmp:
                res.append(w)
            
            return ' '.join(res)
            
    //items为以列表返回可遍历的(键, 值) 元组数组
                    
    //作者：Hanxin_Hanxin
    //链接：/sorting-the-sentence/solution/cpython3-mo-ni-by-hanxin_hanxin-a1or/

## 大牛的思路(c++语言) ##

class Solution {
    public:
        string sortSentence(string s) {
            vector<pair<int,string>> v;
            for (int i = 0; i < s.size(); i++) {
                string word;
                while (i < s.size() && s[i] != ' ') {
                    word += s[i++];
                }
                int pos = word.back() - '0';
                v.emplace_back(pos, word.substr(0, word.size() - 1));
            }
    
            sort(v.begin(), v.end());
            string ans;
            for (auto& t : v) {
                ans += t.second + ' ';
            }
            ans.pop_back();
            
            return ans;
        }
    };
    //csdn---weixin_43203889/article/details/116868487

# 参考资料 #

[leetcode][]  
[csdn][]  
[cplus—string][cplus_string]

[5742.]: https://leetcode-cn.com/problems/sorting-the-sentence/
[leetcode]: https://leetcode-cn.com/problems/sorting-the-sentence/solution/cpython3-mo-ni-by-hanxin_hanxin-a1or/
[csdn]: https://blog.csdn.net/weixin_43203889/article/details/116868487
[cplus_string]: http://www.cplusplus.com/reference/string/string/