九度oj 題目1369 字串的排列

2022-11-24 15:41:45 字數 1407 閱讀 2484

題目1369:字串的排列

時間限制:1 秒

記憶體限制:32 兆

特殊判題:

提交:3257

解決:820

題目描述:

輸入一個字串,按字典序列印出該字串中字元的所有排列。例如輸入字串abc,則列印出由字元a,b,c所能排列出來的所有字串abc,acb,bac,bca,cab和cba。

輸入:

每個測試案例包括1行。

輸入一個字串,長度不超過9(可能有字元重複),字元只包括大小寫字母。

輸出:

對應每組資料,按字典序輸出所有排列。

樣例輸入:

abc

bca

樣例輸出:

abc

acbbac

bcacab

cbaabc

acbbac

bcacab

cba直接呼叫next_permutation()全排列函式

1 #include 2 #include 3 #include 4 #include 5

using

namespace

std;

6int

main()while (next_permutation(s, s +strlen(s)));13}

14return0;

15 }

dfs解決:

1 #include 2 #include 3 #include 4 #include 5 #include 

6 #include

7using

namespace

std;

8char a[10], s[10];9

bool visit[10

];10

setst;

11string

str;

12int

n;13

14void dfs(int

depth)

20for(int i = 0; i < n; i++)27}

28}2930

intmain()

40return0;

41 }

這種方法超記憶體了。。。由於用了set使得不輸出重複串,因此記憶體佔用大,無法ac。將string型別改成char*型別可以省記憶體。。c語言沒學好,修改不成功。。。以後再說。