剑指27：字符串的全排列
字符串的排列
http://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
字典序法、递归法的C++语言实现：
////////////////////////////////////////
①最牛逼的字典序法：
1、从右向左找到第一个正序对（array[i]<array[i+1]，因为没有等号，去掉重复的排列2、从i开始向右搜索，找到比array[i]大的字符中最小的那个，记为array[j]
3、交换array[i]和array[j]
4、将i后面的字符反转
这就得到了字典序的下一个排列。
////////////////////////////////////////
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> res;
if(str.size() == 0)
return res;
sort(str.begin(),str.end());
char *array = new char[str.size()];
strcpy(array,str.c_str());
//sort(array,array+str.size(),less<int>());//greater<int>()升序可省
string s(array);
res.push_back(s);
while(true){
s = nextstring(s);
if(s.compare("finish"))//相同返回0，小于返回负数
res.push_back(s);
else
break;
}
return res;
}
string nextstring(string str) {
char *array = new char[str.size()];
strcpy(array,str.c_str());
int len = str.size();
int i = len-2;
for(;i>=0 && array[i]>=array[i+1];i--);
if(i == -1)
return "finish";
int j = len-1;
for(;j>=0 && array[j]<=array[i];j--);
char temp = array[i];
array[i] = array[j];
array[j] = temp;
for(int a = i+1,b = len-1;a < b;a++,b--){
temp = array[a];
array[a] = array[b];
array[b] = temp;
}
string s(array);
return s;
}
}; ////////////////////////////////////////②递归解法思路:
fun(a,b,c) = a+(fun(b,c)) + (a和b交换)b+(fun(a,c)) + (a和c交换)c+(fun(b,a))
fun(b,c) = b+fun(c) + (b和c交换)c+(fun(b))
fun(c) = 1
////////////////////////////////////////
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> res;
if(str.size() == 1)
res.push_back(str);
else{
for(int i = 0;i < str.size();i++){
if(i == 0 || str.at(0) != str.at(i)){
string temp = str.substr(i,1);
str.replace(i,1,str.substr(0,1));
str.replace(0,1,temp);
vector<string> newres = Permutation(str.substr(1));
for(int j = 0;j < newres.size();j++)
res.push_back(str.substr(0,1) + newres[j]);
temp = str.substr(0,1);
str.replace(0,1,str.substr(i,1));
str.replace(i,1,temp);
}
}
}
sort(res.begin(),res.end());
return res;
}
};
投递柠檬微趣等公司10个岗位 >
