BM58. [字符串的排列]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM58. 字符串的排列
题目主要信息:
- 给定一个长度为n的字符串，求其中所有字符的全排列
- 字符串中可能有重复字符，打印顺序任意
- 字符串中只包含大小写字母
具体思路:
都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复数字的全排列类似，只是这道题输出顺序没有要求。但是为了便于去掉重复情况，我们还是应该参照这道数组全排列，优先按照字典序排序，因此排序后重复的字符就会相邻，后续递归找起来也很方便。
依据数组的全排列，使用临时变量去组装一个排列的情况：每当我们选取一个字符以后，就确定了其位置，相当于对字符串中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。
- 终止条件： 临时字符串中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
- 返回值： 每一层给上一层返回的就是本层级在临时字符串中添加的元素，递归到末尾的时候就能添加全部元素。
- 本级任务： 每一级都需要选择一个元素加入到临时字符串末尾（遍历原字符串选择）。首先已经加入的元素不能再次加入了，因此我们需要使用额外的vis数组用于记录哪些位置的字符被加入了。同时为了去除重复元素的影响，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了，也不需要将其纳入。
当然与数组全排列类似，递归过程也需要回溯，比如说对于字符串“abbc”，如果事先在临时字符串中加入了a，后续子问题只能是"bbc"的全排列接在a后面，对于b开头的分支达不到，因此也需要回溯：将临时字符串刚刚加入的字符pop掉，同时vis修改为没有加入，这样才能正常进入别的分支。参考下图所示：
代码实现:
class Solution {
public:
void recursion(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;
if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
continue; //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
vis[i] = 1; //标记为使用过
temp.push_back(str[i]); //加入临时字符串
recursion(res, str, temp, vis);
vis[i] = 0; //回溯
temp.pop_back();
}
}
vector<string> Permutation(string str) {
sort(str.begin(), str.end()); //先按字典序排序，使重复字符串相邻
vector<int> vis(str.size(), 0); //标记每个位置的字符是否被使用过
vector<string> res;
string temp;
recursion(res, str, temp, vis); // 递归获取
return res;
}
};
复杂度分析：
- 时间复杂度：
，全排列的全部情况为n!，每次递归过程都是遍历字符串查找元素，这里是
- 空间复杂度：
，递归栈的最大深度为字符串长度n，临时字符串temp的空间也为
投递传音控股等公司10个岗位 >
