字符串的排列&&翻转单词顺序列

字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

分析：

这是个递归求解的问题。对于字符串的排列问题。如果能生成n-1个元素的全排列，就能生成n个元素的全排列。对于只有1个元素的集合，可以直接生成全排列。全排列的递归终止条件很明确，只有1个元素时，循环终止。

思路：

       把一个字符串看成两部分组成：第一部分为第一个字符，第二部分为后面的所有字符。

1. 首先求出所有可能出现在第一位置的字母，即begin与后面所有与它不同的字母进行交换
2. 固定第一个字母，求后面字母的全排序，此时仍把后面的字符看成两部分，第一个字符和后面的字符，然后重复上述步骤。（递归）

实现

//字符串的排列
	void PermutationCore(string str,int pos,vector<string>& ret)
	{
		if(pos == str.size()-1)
		{
			ret.push_back(str);
			return ;
		}
		
		for(int i=pos; i<str.size(); i++)
		{
			//从每个自串的第二个字符开始异常与第一个字符交换，然后继续处理子串。注意：这里也可能存在重复的数据。
			if(i != pos && str[i] ==str[pos])
			{
				continue;
			}
			swap(str[pos],str[i]);
			PermutationCore(str,pos+1, ret);//递归处理子串
		}
		
	}

    vector<string> Permutation(string str) 
	{
        vector<string> ret;
		if(str.size() > 0)
		{
			PermutationCore(str,0,ret);
		}

		return ret;
    }

翻转单词顺序列

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

分析：

翻转单词顺序，首先找到每个单词，然后进行翻转。  

这里利用str的基本操作，一个字母一个字母进行处理

实现

//翻转单词顺序列
	//一个一个字母进行处理
    string ReverseSentence(string str) 
	{
		string ret = ""; 
		string tmp = "";
		for(size_t i=0; i<str.size(); ++i)
		{
			if(str[i] == ' ')
			{
				ret = " "+tmp+ret;
				tmp = "";
			}
			else
			{
				tmp += str[i];
			}
		}
		ret = tmp +ret;
		return ret;
    }