烟台建设信息网站营销模式有哪些 新型
字符串的排列_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
class Solution {
public:set<string> res; // 去重string temp;void dfs(string &s, vector<bool>& book, int index){if(index == s.size()){res.insert(temp);return;}for(int i = 0; i < s.size(); i++){if(book[i]){book[i] = false;temp+=s[i];dfs(s, book, index+1);temp.pop_back();book[i] = true;}}}vector<string> Permutation(string str) {vector<bool> book(str.size(), true); // 标志位dfs(str, book, 0);vector<string> ress;for(auto &e : res){ress.push_back(e);}return ress;}
};数据范围：n<10n<10
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。
示例1
输入：
"ab"
返回值：
["ab","ba"]
说明：
返回["ba","ab"]也是正确的
示例2
输入：
"aab"
返回值：
["aab","aba","baa"]
示例3
输入：
"abc"
返回值：
["abc","acb","bac","bca","cab","cba"]
示例4
输入：
""
返回值：
[""]
思路：
都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复项数字的全排列类似，只是这道题输出顺序没有要求。但是为了便于去掉重复情况，我们还是应该参照数组全排列，优先按照字典序排序，因为排序后重复的字符就会相邻，后续递归找起来也很方便。
使用临时变量去组装一个排列的情况：每当我们选取一个字符以后，就确定了其位置，相当于对字符串中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。
- 终止条件： 临时字符串中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
- 返回值： 每一层给上一层返回的就是本层级在临时字符串中添加的元素，递归到末尾的时候就能添加全部元素。
- 本级任务： 每一级都需要选择一个元素加入到临时字符串末尾（遍历原字符串选择）。
递归过程也需要回溯，比如说对于字符串“abbc”，如果事先在临时字符串中加入了a，后续子问题只能是"bbc"的全排列接在a后面，对于b开头的分支达不到，因此也需要回溯：将临时字符串刚刚加入的字符去掉，同时vis修改为没有加入，这样才能正常进入别的分支。
具体做法：
- step 1：先对字符串按照字典序排序，获取第一个排列情况。
- step 2：准备一个空串暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的字符被加入了。
- step 3：每次递归从头遍历字符串，获取字符加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用，也不需要将其纳入。
- step 4：进入下一层递归前将vis数组当前位置标记为使用过。
- step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入字符串的元素，
- step 6：临时字符串长度到达原串长度就是一种排列情况。
图示：