网站机房建设,wordpress 怎么加载js,中国电信视频app下载,必要 网站字符串的排列_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目#xff0c;配有官方题解#xff0c;在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/fe6b651b66ae47d7ac…字符串的排列_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目配有官方题解在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
描述
输入一个长度为 n 字符串打印出该字符串中字符的所有排列你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。 class Solution {
public:setstring res; // 去重string temp;void dfs(string s, vectorbool 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;temps[i];dfs(s, book, index1);temp.pop_back();book[i] true;}}}vectorstring Permutation(string str) {vectorbool book(str.size(), true); // 标志位dfs(str, book, 0);vectorstring ress;for(auto e : res){ress.push_back(e);}return ress;}
}; 数据范围n10n10 要求空间复杂度 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临时字符串长度到达原串长度就是一种排列情况。
图示
