题目描述：
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
示例：
输入：
"aab"
返回值：
["aab","aba","baa"]
解题思路：
本题考察算法-搜索算法的使用。具体实现列了三种写法：
解法一：next_permutation函数
- 使用STL内置算法next_permutation，该函数会将字符串转换为下一排列。
- 如果对字符串先执行了排序，再循环调用next_permutation，直至字符串反序，就相当于获得了字符串从正序到反序的全排列。
解法二：仿写next_permutation函数
- 考虑到很多同学想要了解next_permutation的原理逻辑，进行了仿写，仅供参考。
- 通过for循环，使得i最终位置是从右到左的首个正序的起始点。
- 若i小于0，说明此时字符串已是反序，全排序已完毕。
- 再通过for循环，找到比i大的字符中最小的那个，i和j交换，这样可满足字典序的全排列顺序。
- i和j交换后，i后面的字符串应该是反序状态，将其反转为正序，再继续找新的排列。
解法三：深度优先遍历DFS
- 先字典序排序，再进行深度优先遍历获取全排列，用递归实现。
- 当临时字符串尺寸与输入字符串尺寸一致时，递归返回，并将当前字符串存入数组。
- 通过for循环，遍历所有元素，当某字符被加入到字符串了，就跳过该字符；当前的字符如果同前一个字符相同，且前面的字符还没用过，也跳过，不然会重复获取相同的字符串。
- 被加入的字符，将vis数组对应位置设1，作标记用，并将其加入临时字符串中。
- 某深度遍历完毕后，回溯到上一层，换不同的组合得到新的排列。
- 以此类推，直到所有的排列获取。
测试代码：
解法一：next_permutation函数
class Solution { public: vector<string> Permutation(string str) { vector<string> ans; // 判空 if (str.empty()) return ans; // 排序 sort(str.begin(), str.end()); // 全排列，next_permutation会将str转为下一个排列 do { ans.push_back(str); } while (next_permutation(str.begin(), str.end())); return ans; } };
解法二：仿写next_permutation函数
class Solution { public: vector<string> Permutation(string str) { vector<string> ans; // 判空 if(str.size() == 0) return ans; // 排序 sort(str.begin(),str.end()); // 全排列 do { ans.push_back(str); } while (nextPermutation(str)); return ans; } // 变换为下个排列 bool nextPermutation(string &str) { // len为字符串长度 int len = str.size(); // 通过for循环，使得i最终位置是从右向左的首个正序的起始点 int i = len-2; for(;i>=0 && str[i]>=str[i+1];i--); // 若i小于0，说明此时字符串已是反序，全排列已完毕 if(i < 0 ) return false; // 通过for循环，找到比i大的字符中最小的那个，i和j交换 // 交换后，i后面的字符串应该是反序状态 int j = len-1; for(;j>=0 && str[j]<=str[i];j--); char temp = str[i]; str[i] = str[j]; str[j] = temp; // 将i后面的字符串反转成正序，继续找新的排列 for(int a = i+1,b = len-1;a < b;a++,b--) { temp = str[a]; str[a] = str[b]; str[b] = temp; } return true; } };
解法三：深度优先遍历DFS
class Solution { public: // 深度优先遍历 void DFS(vector<string> &res, string &str, string &temp, vector<int> &vis) { // 临时字符串满了加入输出 if(temp.length() == str.length()) { res.push_back(temp); return; } // 遍历所有字符选取一个加入 for(int i = 0; i < str.length(); i++) { // 如果该字符已经被加入了则不需要再加入了 if(vis[i]) continue; // 当前的字符str[i]与同一层的前一个字符str[i-1]相同且str[i-1]还没用过，则跳过，避免重复 if(i > 0 && str[i - 1] == str[i] && !vis[i - 1]) continue; // 标记为使用过 vis[i] = 1; // 加入临时字符串 temp.push_back(str[i]); // 深度优先遍历 DFS(res, str, temp, vis); // 回溯 vis[i] = 0; temp.pop_back(); } } vector<string> Permutation(string str) { // 先按字典序排序，使重复字符串相邻 sort(str.begin(), str.end()); // 标记每个位置的字符是否被使用过s vector<int> vis(str.size(), 0); vector<string> res; string temp; // 深度优先遍历 DFS(res, str, temp, vis); return res; } };
