输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
/*
问题：全排列（含重复元素，且要求按字典序输出）
方法一：交换法，递归
用哈希表记录，以解决存在重复元素的全排列问题
*/
class Solution
{
public:
vector<string> Permutation(string str)
{
vector<string> result;
if(str.empty()) return result;
per(str, 0, result);
sort(result.begin(), result.end()); //排序，以便之后产生字典序的全排列(这里是产生序列之后再排序，通过改进算法可以实现按字典序push)
return result;
}
private:
void per(string& str, int begin, vector<string>& result)
{
if(begin >= str.size()-1)
{
result.push_back(str);
return;
}
else
{
unordered_set<char> record; //记录出现过的字符
for(int i = begin; i<str.size(); i++) //产生排列的多个分支
{
if(record.find(str[i]) == record.end()) //只和没交换过的交换
{
record.insert(str[i]);
swap(str[begin], str[i]); //与后面元素交换，以产生不同字符开头的排列
per(str, begin+1, result); //递归产生分支的深度
swap(str[begin], str[i]); //归位，以便下次交换
}
}
}
}
};
/*
方法二：dfs(掌握)
用map记录，以解决存在重复元素的全排列问题
*/
class Solution
{
public:
vector<string> Permutation(string str)
{
vector<string> result;
if(str.empty()) return result;
string path;
map<char,int> counter; //用map时，key值存储为有序的，最后输出的排列也是有序的
// sort(str.begin(), str.end()); //上面用了map,故这里无需先sort了
for(char a:str) counter[a]++; //统计str中各数出现的次数，没有key的时候会自动创建
dfs(str, result, path, counter);//递归
return result;
}
private:
void dfs(string& str, vector<string>& result, string& path, map<char, int>& counter)
{
if(path.size() == str.size()) //到达树的末尾，将单路径数组push到结果向量中
{
result.push_back(path);
return;
}
for(auto& p:counter) //for循环带来的是树宽度方向的延伸，即产生同一层的多个分支
{
if(p.second>0) //如果该元素没有被取完（某个元素可能会出现多次）
{
path.push_back(p.first);
p.second--; //已经取了这个元素，统计数减一
dfs(str, result, path, counter); //继续往深度方向延伸
path.pop_back(); //回溯，给其他分支腾空间！！
p.second++;
}
}
}
};
