题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
class Solution {
public:void perm(int pos, string str, set<string> ret){if(pos + 1 == str.length()){ret.insert(str);return;}// for循环和swap的含义：对于“ABC”，// 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'// 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'// 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'for(int i=pos; i<str.length(); i++){swap(str[pos], str[i]);perm(pos+1, str, ret);swap(str[pos], str[i]);// 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"// 然后进行第三次交换，才能得到"CBA"}}vector<string> Permutation(string str) {if(str.empty())return {};//用set可以进行去重，并且可以达到按字母顺序排序set<string> ret;perm(0, str, ret);return vector<string>({ret.begin(), ret.end()});}
};