﻿ 【剑指Offer-分解让复杂问题简单化】面试题38：字符串的排列

## 思路1

``````class Solution {
public:
vector<string> Permutation(string str) {
vector<string> ans;
if(str=="")
return ans;

int visit[str.length()];
memset(visit, 0, sizeof(visit));
string cur;
PermutationCore(str, ans, cur, visit);
ans = RemoveRepeat(ans);
return ans;
}

void PermutationCore(string str, vector<string>& ans, string cur, int* visit){
if(cur.length()==str.length()){
ans.push_back(cur);
return;
}

for(int i=0; i<str.length(); i++){
if(!visit[i]){
visit[i] = 1;
cur+=str[i];
PermutationCore(str, ans, cur, visit);
cur = cur.substr(0, cur.length()-1);    //把前一步加的字符删掉
visit[i] = 0;
}
}
}

vector<string> RemoveRepeat(vector<string> ans){
set<string> s;
for(int i=0; i<ans.size(); i++)
s.insert(ans[i]);

vector<string> newAns;
for(set<string>::iterator it=s.begin();it!=s.end(); it++)
newAns.push_back(*it);
return newAns;
}
};
``````

## 思路2

``````class Solution {
public:
vector<string> Permutation(string str) {
vector<string> ans;
if(str=="")
return ans;

int cur = 0;
PermutationCore(str, ans, cur);
ans = RemoveRepeat(ans);
return ans;
}

void PermutationCore(string str, vector<string>& ans, int cur){
if(cur==str.length()){
ans.push_back(str);
return;
}

for(int i=0; i<str.length(); i++){
swap(str, i, cur);
PermutationCore(str, ans, cur+1);
swap(str, i, cur);
}
}

void swap(string& str, int a, int b){
char t = str[a];
str[a] = str[b];
str[b] = t;
}

vector<string> RemoveRepeat(vector<string> ans){
set<string> s;
for(int i=0; i<ans.size(); i++)
s.insert(ans[i]);

vector<string> newAns;
for(set<string>::iterator it=s.begin();it!=s.end(); it++)
newAns.push_back(*it);
return newAns;
}
};
``````