题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
第一想法
- 大小写的相同字母构成的字符串是否算同一个?比如说
AAc和aaC? - 无重复的字母排列是n!(按字典序输出)
- 计算机中没有字典序就用ACSII码排序吧,但是aa和AA哪个排前面?
- c++中的字符串如何使用
- 提示中有动态规划,那么问题来了,动态规划是什么?
我的想法
像之前找路径那样的想法我已经想到了。在Vsc里面写了一些。
void CA(string str){
if(str.length() == 0){
return ;
}
if(str.length() == 1){
cstr.push_back(str[0]);
fstr.push_back(cstr);
}
for(int i = 0; i < str.length(); ++i){
cstr.push_back(str[i]);
CA(delete_char(str,str[i]));
cstr.pop_back();
}
return ;
}
- 就像那棵树一样,只不过一个是左右子树的push与pop,这个是有好多子树来for()
问题在于我选择的是新建空间,比如说{A,B,C}
A -> vec
然后要把A删掉的BC字符串放进去,写删除str中char的函数的时候出现了一些些问题,就看讨论区有没有更简易的办法.
看了讨论区
本来以为要自己手动实现sort函数,结果你告诉我可以直接调用???我懵了.
这是递归回溯法的解法.只是它是用的swap,我是新建再放进去的办法
class Solution {
public:
vector<string> result;
vector<string> Permutation(string str) {
if(str.length() == 0)
return result;
Permutation(str, 0);
//保证是字典序
sort(result.begin(), result.end());
return result;
}
void Permutation(string str, int begin){
if(begin == str.length() - 1){
result.push_back(str);
return ;
}
for(int i = begin; str[i] != '\0';i++){
//begin != i;因为首个交换的即是它本身，必定相等。
//我们要找出之后相等的，跳过（重复的就不用交换了）。
if(begin != i && str[i] == str[begin])
continue;
swap(str[i],str[begin]);
Permutation(str,begin + 1);
//因为在这个for中,是同一层的.之前交换过去的begin头还要交换回来
//首元素,譬如说A,与B交换之后要交换回来再和C交换
swap(str[i],str[begin]);
}
}
};
字典序全排列博客
https://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html
以下是实现代码
class Solution {
public:
/*
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
3）对换pj，pk
4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。
*/
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> res;
int len = str.length();
if(len == 0)
return res;
else if(len == 1){
res.push_back(str);
return res;
}
str = sortStr(str);
res.push_back(str);
int left = -1, right = len - 1;
while(true){
left = -1;
for(int i = len - 1; i > 0; --i){
if(str[i - 1] < str[i]){
left = i - 1;
break;
}
}
if(left == -1)
break;
for(int j = left + 1; j < len; ++j){
if(str[j] > str[left])
right = j;
}
swap(str[left], str[right]);
for(int i = left + 1,j = len - 1; i < j; i++,j--){
swap(str[i], str[j]);
}
res.push_back(str);
}
return res;
}
string sortStr(string str){
int len = str.length();
char tmp;
for(int i = 0; i < len - 1; ++i)
for(int j = 0;j < len - 1 - i; ++j)
if(str[j] > str[j + 1]){
tmp = str[j];
str[j] = str[j + 1];
str[j + 1] = tmp;
}
return str;
}
};
字典排序
- 从小到大排序
- 从后往前,找到后面那个大于前面那个的位置,前面的下标为left,
- 从left + 1开始向后找,找到最后一个大于left位置的下标为right
- 交换left / right 的值,
- 将 left后的序列逆序.
- 得到的就是字典序列中原序列后一个序列.
eg.
12398745 ---- 45 然后变成12398754
12398754 ---3和9
找到 4交换 12498753
reverse 98753 是35789
12398754的后一个即为 12435789
