最近听面试的同学回来讲到有一个笔试题目,关于字符串全排列的,比如abbccd,求这个字符串的所有排列可能,要排除重复的,并且ac不能相邻,我之前已经写了一个关于递归解决全排列的文章,递归直接对位置进行交换,并且前提是没有重复的字符如abc,abcde,所以abbccd就不行了。
这里还有一种解决全排列的方法,字典序算法:
1:从倒数第二个元素开始,从右往左找到第一个小于其后元素的元素,用m下标之
2:从最后往左找,直到找到第一个大于上一步中找到元素的元素,用k下标之
3:交换前面两步找到的两个元素之值
4:将m下标的元素后面部分做逆序,因为它是后面几个元素的最大排列方式,要让它成为最小
经过上面四个步骤我们就可以找到一个字符串的字典序的下一个字符串,我们将字符串排列为最小,然后向后查找,一直查找到逆序最大,这样就可以了,对于重复的也可解决,关键在于判断的时候那个>要换成>=,
至于ac不相邻,只需要在输出的时候判断下就可以了,查找ac||ca子串。程序如下,经过g++测试:
#define MAXSIZE 256
#include
using namespace std;
template
inline void Swap(T& a,T& b)
{//exchange a and b
T temp = a;a = b;b = temp;
}
void sort(char *str)
{
int len = strlen(str);
int i,j;
for(i = 0;i < len;i++)
for(j = len - 1;j >= i;j--)
if(str[j] < str[j-1])
Swap(str[j],str[j-1]);
if(strstr(str,"ac")==NULL && strstr(str,"ca")==NULL)
printf("%s\n",str);
while(1){
int m=len-2;
while(str[m]>=str[m+1])
{
m--;
}
if(m == -1)
break;
int k=len-1;
while(str[m]>=str[k]) //here > will left same string,so must >=
{
k--;
}
Swap(str[m],str[k]);
int p=m+1;
int q=len-1;
while(p {
Swap(str[p],str[q]);
p++;
q--;
}
if(strstr(str,"ac")==NULL && strstr(str,"ca")==NULL)
printf("%s\n",str);
}
return;
}
int main()
{
char str[MAXSIZE];
scanf("%s",str); sort(str);
return 0;
}
阅读(1264) | 评论(0) | 转发(0) |