输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
一开始的做法，回溯法模拟了一遍全排列；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
vector<bool> used;
public:
vector<string> permutation(string s) {
vector<string> result;
unordered_set<string> tempResult;
string temp="";
for(auto c:s){used.push_back(false);}
huiSu(tempResult,s,temp);
for(auto c:tempResult){
result.push_back(c);
}
return result;
}
void huiSu(unordered_set<string>& result,string& s,string& temp){
if(temp.length()==s.length()){
result.insert(temp);
}
for(int j=0;j<s.length();j++){
if(used[j]){
continue;
}
temp.push_back(s[j]);
used[j]=true;
huiSu(result,s,temp);
used[j]=false;
temp.pop_back();
}
}
};
|
对于有重复元素的情况，我使用了set集合先把所有的结果加进去，然后再返回到vector中
还可以先将字符串排序，排序后相同的元素在一起，然后把他们看成一个即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public:
vector<string>res;
void backtrack(string s,string& temp,vector<bool>& used)
{
if(temp.size()==s.size())
{
res.push_back(temp);
return;
}
for(int i=0;i<s.size();i++)
{
if(!used[i])
{
if(i>=1&&s[i-1]==s[i]&&!used[i-1])
continue;
temp.push_back(s[i]);
used[i]=true;
backtrack(s,temp,used);
used[i]=false;
temp.pop_back();
}
}
}
vector<string> permutation(string s) {
if(s.size()==0)
return{};
string temp="";
sort(s.begin(),s.end());
vector<bool>used(s.size());
backtrack(s,temp,used);
return res;
}
};
|
进行通过字符交换来实现全排列,然后使用unordered_set去重（这个去重与上面的作用完全不一样），如果某个已经交换过了，就不用在交换了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<string> permutation(string s) {
vector<string> res;
dfs(s, res, 0);
return res;
}
void dfs(string &s, vector<string> &res, int depth)
{
if(depth >= s.size()-1)
{
res.push_back(s);
return ;
}
unordered_set<char> used;
for(int i = depth; i < s.size(); ++i)
{
if(used.find(s[i]) != used.end()) continue;
used.insert(s[i]);
swap(s[depth],s[i]);
dfs(s, res, depth+1);
swap(s[depth],s[i]);
}
}
};
作者：zrita
链接：https:
|