字符全排列
【题目描述】
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。
我们假设对于小写字母有‘a’ <‘b’ < … <‘y’<‘z’,而且给定的字符串中的字母已经按照从小到大的顺序排列。
【输入描述】
只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到6之间。
【输出描述】
输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。
【样例输入】
abc
【样例输出】
abc
acb
bac
bca
cab
cba
【分析】
(1)比较经典的搜索回溯题目,不同的是由数字改成了字符
(2)定义一个输出函数,一旦满足要求就输出
(3)输入保证由小到大
【参考代码1】
char str[10],ans[10]; //用户输入的字符串,结果数组
bool flag[10]; //标记数组,用来标记这个字符有没有出现过
if(step==n) //如果步数到了n(长度),就输出ans
ans[step]='\0'; //加上结尾,防止过多输出
for(int i=0;i<n;i++) //枚举字符,从0开始
if(flag[i]==0) //如果当前的字符没有被使用过
ans[step]=str[i]; //把当前字符放到结果数组当中
memset(flag,0,sizeof(flag)); //初始化标记数组
n=strlen(str); //测量字符串长度,用来判断是到头
另外一个框架的版本:
【参考代码2】
char ans[10001];//存放答案的字符数组
bool flag[10001]={0}; //标记这个数有没有被使用过,0表示没有使用
for(int i=0;i<len;i++) //字符数组从0开始枚举
if(flag[i]==0) //如果当前这个字符没有使用过
ans[k]=s[i]; //把当前字符放到结果字符数组里
ans[len]='\0'; //在末尾加上结束标识符
dfs(k+1); //否则,就继续枚举下一个位置
扫描二维码推送至手机访问。
版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。