-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquestion38.cpp
More file actions
50 lines (47 loc) · 1.25 KB
/
Copy pathquestion38.cpp
File metadata and controls
50 lines (47 loc) · 1.25 KB
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串 abc,则打印出由字符 a,b,c 所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba。
Xiaobin Tian;
*/
#include<vector>
#include<algorithm>
#include<unordered_set>
using namespace::std;
class Solution {
vector<string> Permutationsubstring(string str, int end){
vector<string> result;
unordered_set<char> set;
if(end == 1){
string a = {str[end-1]};
result.push_back(a);
return result;
}
for(int i = end-1; i >= 0; --i){
if(i != end-1 && set.find(str[i]) != set.end())
continue;
set.insert(str[i]);
auto temp = str[end-1];
str[end-1] = str[i];
str[i] = temp;
auto temp_result = Permutationsubstring(str, end-1);
for(int j = 0; j < temp_result.size(); ++j){
temp_result[j] = temp_result[j] + str[end-1];
result.push_back(temp_result[j]);
}
temp = str[end-1];
str[end-1] = str[i];
str[i] = temp;
}
return result;
}
public:
vector<string> Permutation(string str) {
vector<string> result;
if(str.length() == 0)
return result;
result = Permutationsubstring(str, str.length());
sort(result.begin(), result.end());
return result;
}
};