首页 > 代码库 > 字符串的排列

字符串的排列

字符串的排列


  • 题目描述:

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

  • 分析:

    虽然题目举例的输入时abc,但并没有说明输入的字符串是按字典序的,所以在打印中的字典序可能会需要一个排序过程。首先,我们可以把字符串看成两部分:第一个字符和它后边的剩余字符组成的字符串。所以在求所有排列的过程中我们可以先选择一个字符作为首字母,即将第一个字符和后边的所有字符一次交换,然后固定第一个位置的字符,再对其后边的所有字符求所有排列。显然这是一个递归的过程。注意: 递归需要终止的条件,在这里为固定的字符为字符串的最后一个字符。

    //方法一:通过一个set使string序列变成字典序,并且可以消除重复的序列
    
    void permutation(set<string> &res,string &str,int begin,int end)
    { 
    	 if (begin == end)
    		res.insert(str);
    
    	for (int i = begin; i <= end; ++i)
    	{
    		swap(str[begin], str[i]);// 容器string中存在函数swap直接交换string中的两个元素
    		permutation(res, str, begin + 1, end);
    		swap(str[begin], str[i]);
    	}
    }
    
    vector<string> Permutation(string str)
    {
    	vector<string> result;
    	set<string> res;
    
    	permutation(res, str, 0, str.end());
    
    	for (auto &s : res)
    		result.push_back(s);
    	return result;
    }
    
    // 方法二:使用sort先进行排序,但要注意消除重复的序列
    
    void permutation(vector<string> &res, string &str, int begin, int end)
    {
    	if (begin == end)
    		res.push_back(str);
    
    	for (int i = begin; i <= end; ++i)
    	{
    		if (i != begin && str[i] == str[begin]) // 固定某一位的时候遇到相同字符不交换,避免重复
    			continue;
    		swap(str[begin], str[i]);
    		permutation(res, str, begin + 1, end);
    		swap(str[begin], str[i]);
    	}
    }
    
    vector<string> Permutation(string str)
    {
    	vector<string> result;
    
    	permutation(result, str, 0, str.size() - 1);
    	sort(result.begin(), result.end());
    
    	return result;
    }
    

字符串的排列