这道题和书上的 case 略有区别，在书上的例子中，不会有重复的元素，但是在这里会有重复的元素。所以书中不断将第一个元素和后面元素进行交换的方法会出现问题。
在这里，使用了类似 Leetcode 中 47 题 的 方法 ，在判断是否要将元素加入字符串中的时候，如果它和它的前一个元素相同，那么如果前一个元素被使用过，它才能被使用。这样，就杜绝了系统将两个元素相同当做不同元素的问题。
具体的程序中，使用了一个 char* 来构造不同的排列，使用了 string 的复制构造函数来将每次构造好的字符串写入返回的 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
36
| class Solution {
private:
bool* used;
string* str;
int strLen;
vector<string>* result;
char* s;
public:
vector<string> Permutation(string str) {
strLen=(int)(str.size());
result=new vector<string>();
if(strLen==0) return *result;
this->str=&str;
sort(str.begin(),str.end());
used=new bool[strLen];
memset(used,false,strLen);
s=new char[strLen+1];
s[strLen]='\0';
GetPermutation(0);
return *result;
}
void GetPermutation(int pos){
if(pos>=strLen){
result->push_back(string(s));
return;
}
int i=0;
for(;i<strLen;i++){
if(used[i] || (i>0 && (*str)[i-1]==(*str)[i] && !used[i-1])) continue;
s[pos]=(*str)[i];
used[i]=true;
GetPermutation(pos+1);
used[i]=false;
}
}
};
|