-
Notifications
You must be signed in to change notification settings - Fork 2
/
剑27-字符串的排列
35 lines (32 loc) · 1.14 KB
/
剑27-字符串的排列
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
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
class Solution {
public:
vector<string> Permutation(string str) {
Permutation(str, str.size(),0);
return result;
}
private:
vector<string> result;
bool IsDuplicate(string str, int num1, int num2){
while(num1 < num2){
if(str[num1] == str[num2])
return true;
num1++;
}
return false;
}
void Permutation(string str, int size, int begin){
if(begin == size-1)
result.push_back(str);
sort(str.begin()+begin,str.end());//按照增长的顺序输出
for(int i=begin; i<size; i++){
if(IsDuplicate(str, begin, i)) continue;
swap(str[i],str[begin]);
Permutation(str, size, begin+1);
swap(str[i],str[begin]);
}
}
};