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

字符全排列

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

【题目描述】

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。
我们假设对于小写字母有‘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);  //从第一个位置开始  
}