首页 > 代码库 > 【剑指offer】字符串的排列
【剑指offer】字符串的排列
转载请注明出处:http://blog.csdn.net/ns_code/article/details/26390551
- 题目描写叙述:
输入一个字符串,按字典序打印出该字符串中字符的全部排列。比如输入字符串abc,则打印出由字符a,b,c所能排列出来的全部字符串abc,acb,bac,bca,cab和cba。
- 输入:
每一个測试案例包含1行。
输入一个字符串,长度不超过9(可能有字符反复),字符仅仅包含大写和小写字母。
- 输出:
相应每组数据,按字典序输出全部排列。
- 例子输入:
abc
BCA
- 例子输出:
abc
acb
bac
bca
cab
cba
ABC
ACB
BAC
BCA
CAB
CBA
昨晚折腾了一个晚上。连这一道题目都没AC,太受打击了!这里倒不是算法的问题,主要是既要考虑输出的字符串按字典序排列,又要去掉反复的字符串。
本想直接在不保存全部字符串的前提下。直接依照要求输出字符串,但折腾了一晚上,还是决定放弃了。依旧是使用最直接的方法。以空间换取结果。将全部的字符串保存到一个字符串数组中,因为全排列后的字符串数最大为9!
=362880,故开辟一个362900大的字符串数组用来保存这些字符串,而后对这些字符串进行排序,先用了选择排序。通过strcpy字符串进行排序,结果争取,但第三组測试用例超时,无奈。最后还是要用系统自带的qsort快排函数,这次AC了。顺带也复习了下qsort的使用方法。了解的更深入了些!
AC代码:
#include<stdio.h> #include<string.h> #include<stdlib.h> char result[362900][10]; int count = 0; //排列字符串的个数 /* 交换两个字符 */ void swap(char *a,char *b) { char temp = *a; *a = *b; *b = temp; } /* 对字符串str从begin開始的后面的字符进行排列 */ void Permutation(char *str,int begin) { int len = strlen(str); if(begin == len-1) { strcpy(result[count++],str); return; } int i; for(i=begin;i<len;i++) { swap(&str[begin],&str[i]); Permutation(str,begin+1); swap(&str[begin],&str[i]); } } /* 将Permutation封装起来 */ void PermutationAllChar(char *str) { if(str == NULL) return ; Permutation(str,0); } /* 比較str1和str2的大小 */ int myCompare(const void *a,const void *b) { char *s1 = (char *)a; char *s2 = (char *)b; return strcmp(s1,s2); } int main() { char str[10]; while(gets(str)) { PermutationAllChar(str); //快排对字符串数组进行字典排序 //之前採用选择排序,并通过复制字符串排序。OJ上报超时 //改用快排,AC。 qsort(result,count,10*sizeof(char),myCompare); //跳过反复字符串 int i; for(i=0;i<count;i++) { if(strcmp(result[i],result[i+1]) == 0) continue; puts(result[i]); } //下一个字符的排列依旧从result数组的開始处開始存放 count = 0; } return 0; }
/**************************************************************
Problem: 1369
User: mmc_maodun
Language: C
Result: Accepted
Time:220 ms
Memory:8000 kb
****************************************************************/
【剑指offer】字符串的排列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。