题目描述
给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。
我们假设对于小写字母有 a<b<…<y<z ,而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入格式
输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在 1 到 6 之间。
输出格式
输出这个字符串的所有排列方式,每行一个排列。
要求字母序比较小的排列在前面。
数据范围
字符串的长度在 1 到 6 之间
算法1
无需处理字母顺序,直接输出
为什么可以这样?一开始我也很奇怪,明明我还没对输出顺序做处理,它也能够输出正确答案。
原因是,这道题输入的时候,就保证了输入顺序是按字母顺序来的,所以在进行 dfs 时自然就按字母顺序来了
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
char g[N];
int temp[N];
bool check[N];
int n,length; // length 表示字符串长度,k 表示当前 g[] 的位置
string str;
void dfs(int u)
{
if(u==length)
{
// 已经到达最后一个位置
puts(g);
// for(int i=0;i<length;i++) cout<<g[i];
// cout<<endl;
return;
}
for(int i=0;i<length;i++)
{
if(!check[i])
{
g[u] = str[i];
check[i] = true;
dfs(u+1);
check[i] = false;
}
}
}
int main()
{
cin>>str;
length = str.size();
// 从下标为 0 开始
dfs(0);
return 0;
}
算法2
处理字母顺序
万一下次题目输入时不按字母顺序来咋办?此时就得处理输出顺序的问题了
既然输入时不按字母顺序,那我们就让它输入时不按字母顺序
直接上代码(main函数中处理)
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
char g[N];
int temp[N];
bool check[N];
int n,length; // length 表示字符串长度,k 表示当前 g[] 的位置
string str;
void dfs(int u)
{
if(u==length)
{
// 已经到达最后一个位置
puts(g);
// for(int i=0;i<length;i++) cout<<g[i];
// cout<<endl;
return;
}
for(int i=0;i<length;i++)
{
if(!check[i])
{
g[u] = str[i];
check[i] = true;
dfs(u+1);
check[i] = false;
}
}
}
int main()
{
cin>>str;
length = str.size();
for(int i=0;i<length;i++) temp[i] = str[i] - 'a';
sort(temp,temp+length);
for(int i=0;i<length;i++) str[i] = temp[i] +'a';
// 从下标为 0 开始
dfs(0);
return 0;
}