CodingInterview-字符串的排列

这道题和书上的 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;
}
}
};