当前位置：首页 > 题解目录 > 正文内容

字符全排列

亿万年的星光5年前 (2021-01-28)题解目录2450

【题目描述】

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。
我们假设对于小写字母有‘a’ <‘b’ < … <‘y’<‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

【输入描述】
只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

【输出描述】
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。

【样例输入】

abc

【样例输出】

abc
acb
bac
bca
cab
cba

【分析】

(1)比较经典的搜索回溯题目，不同的是由数字改成了字符
(2)定义一个输出函数，一旦满足要求就输出
(3)输入保证由小到大

【参考代码1】

/*
字符全排列
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[10],ans[10]; //用户输入的字符串，结果数组
int n;
bool flag[10]; //标记数组，用来标记这个字符有没有出现过
void dfs(int step)
{
   if(step==n) //如果步数到了n(长度)，就输出ans
   {
       ans[step]='\0'; //加上结尾，防止过多输出
       cout<<ans<<endl;
   }
   for(int i=0;i<n;i++) //枚举字符，从0开始
       if(flag[i]==0) //如果当前的字符没有被使用过
       {
           flag[i]=1; //把当前字符标记为使用过
           ans[step]=str[i]; //把当前字符放到结果数组当中
           dfs(step+1); //搜索下一个位置
           flag[i]=0; //回溯一步
       }
}
int main()
{
   memset(flag,0,sizeof(flag)); //初始化标记数组
   scanf("%s",str); //读入字符串
   n=strlen(str); //测量字符串长度，用来判断是到头
   dfs(0); //注意，此处是从0开始的
   return 0;
}

另外一个框架的版本：

【参考代码2】

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char ans[10001];//存放答案的字符数组
int len; //字符数组长度
bool flag[10001]={0}; //标记这个数有没有被使用过，0表示没有使用
char s[50]; //要读入的数据
int dfs(int k)
{
   for(int i=0;i<len;i++) //字符数组从0开始枚举
   {
       if(flag[i]==0) //如果当前这个字符没有使用过
       {
           flag[i]=1; //当前字符使用过就标记
           ans[k]=s[i]; //把当前字符放到结果字符数组里
           if(k==len-1) //到达边界就输出
           {
               ans[len]='\0'; //在末尾加上结束标识符
               cout<<ans<<endl;
           }
           else
               dfs(k+1); //否则，就继续枚举下一个位置
           flag[i]=0; //回溯一步
       }
   }
}
                                   
int main()
{
 cin>>s;
 len=strlen(s);  
 dfs(0); //从第一个位置开始  
}


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：连词成句

下一篇：字符全排列(2)

相关文章

【题解】苯小猴

【题目描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn是单词中出现次数最...

【题解】约瑟夫问题2

【题解】约瑟夫问题2

【题目描述】M个人围成一圈，每分钟相邻的两个人可以交换位置（只能有一对交换）。求使M个人的顺序颠倒（即每个人左边相邻的人换到右边，右边相邻的人换到左边）所需的最少时间（分钟数）。【输入描述】 ...

质数环

【题目描述】有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开始。例如，下面就是6的一个素数环。1 4 3...

【算法】滑动窗口2—窗口大小可变

【算法】滑动窗口2—窗口大小可变

对于滑动窗口第二类：窗口大小可变类型 图解如下，类似双指针算法。【解题思想】1、字符串 S 中使用双指针的左右指针技巧，初始化 left = right = 0，把索引的...

【题解】2019 T2 公交换乘

【题目描述】著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：1、在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠...

【题解】阳光

【题目描述】给出一个n*n的矩阵，矩阵每个元素数值代表这个位置的阳光情况，给出正整数k，需要我们求出哪一处的k*k 区域的阳光平均值最多，阳光平均值为k*k 区域的阳光总和除于k*k。蒜头君想让我们输...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.