算法2
全排列+剪枝
类似全排列一样去搜索就可以。
剪枝优化:
- 当前字符是否用过
- 当前字符是否严格大于前一个字符
- 当前字符是否超过了当前位置所能放置的最大字符
C++ 代码
#include <cstdio>
#include <cstdlib>
using namespace std;
const char M[] = " abcdefghijklmnopqrstuvwxyz";
int s, t, w, cnt;
char p[30];
bool vis[30];
void dfs(int x)
{
if (x == w + s)
{
if (cnt) puts(p + s);
if (++cnt == 6) exit(0);
return ;
}
for (int i = s; i <= t; ++i)
{
if (cnt == 0) i = p[x] - 'a' + 1;
if (!vis[i] && M[i] > p[x-1] && i <= t - w + 1 + x - s)
{
vis[i] = true;
p[x] = M[i];
dfs(x + 1);
vis[i] = false;
}
}
}
int main()
{
scanf("%d%d%d", &s, &t, &w);
scanf("%s", p + s);
dfs(s);
return 0;
}