题目1369：字符串的排列
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：3257
解决：820
- 题目描述：
-
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串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
直接调用next_permutation()全排列函数1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 int main(){ 7 char s[10]; 8 while(scanf("%s", s) != EOF){ 9 sort(s, s + strlen(s)); 10 do{ 11 printf("%s ", s); 12 }while (next_permutation(s, s + strlen(s))); 13 } 14 return 0; 15 }
dfs解决：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <string> 6 #include <set> 7 using namespace std; 8 char a[10], s[10]; 9 bool visit[10]; 10 set<string> st; 11 string str; 12 int n; 13 14 void dfs(int depth){ 15 if(depth == n){ 16 a[n] = ' '; 17 str = a; 18 st.insert(str); 19 } 20 for(int i = 0; i < n; i++){ 21 if(visit[i] == false){ 22 visit[i] = true; 23 a[depth] = s[i]; 24 dfs(depth + 1); 25 visit[i] = false; 26 } 27 } 28 } 29 30 int main(){ 31 while(scanf("%s", s) != EOF){ 32 st.clear(); 33 n = strlen(s); 34 memset(visit, false, sizeof(visit)); 35 sort(s, s + n); 36 dfs(0); 37 for(set<string>::iterator it = st.begin(); it != st.end(); it++) 38 printf("%s ", (*it).c_str()); 39 } 40 return 0; 41 }
这种方法超内存了。。。由于用了set使得不输出重复串，因此内存占用大，无法ac。将string类型改成char*类型可以省内存。。c语言没学好，修改不成功。。。以后再说。