题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
解题思路
见代码
代码实现
class Solution {
public:
vector
<string
> Permutation(string str
) {
vector
<string
> vecOfStr
;
if(str
.empty()){
return vecOfStr
;
}
permutationHelper(str
, vecOfStr
, 0);
sort(vecOfStr
.begin(), vecOfStr
.end());
return vecOfStr
;
}
private:
void swap(char& firstChar
, char& secondChar
){
char tmp
= firstChar
;
firstChar
= secondChar
;
secondChar
= tmp
;
}
void permutationHelper(string str
, vector
<string
>& vecOfStr
, int begin
){
if(begin
== str
.size() - 1){
if(find(vecOfStr
.begin(), vecOfStr
.end(), str
) == vecOfStr
.end()){
vecOfStr
.push_back(str
);
}
}
else{
for(int i
= begin
; i
< str
.size(); i
++){
swap(str
[i
], str
[begin
]);
permutationHelper(str
, vecOfStr
, begin
+ 1);
swap(str
[i
], str
[begin
]);
}
}
}
};
运行结果
运行时间：5ms 占用内存：492k
