在做字符串相關(guān)問(wèn)題時(shí)，有時(shí)需要遍歷字符串所有可能的排列。比如 abc, 可能有abc, acb, bac, bca....等情況。本文通過(guò)分治的方法脑漫，求得了輸入字符串的所有排列集合，下面對(duì)算法進(jìn)行分析咙崎。
注意：從理論上分析优幸，這是一個(gè)排列組合問(wèn)題，所以復(fù)雜度不會(huì)在多項(xiàng)式時(shí)間褪猛，應(yīng)該是O(N!), 所以當(dāng)輸入字符串超過(guò)7位時(shí)网杆，使用這個(gè)算法將花費(fèi)很長(zhǎng)時(shí)間，請(qǐng)退一步反思求解思路是否有問(wèn)題伊滋。
思路><分治法
找出子問(wèn)題
一個(gè)字符串變量假如是str碳却，既然是str的全排列，那么str的每一個(gè)字符都可以打頭笑旺。那么子問(wèn)題可以是：
求某一個(gè)字符打頭的字符串的全排列追城。
分別求str每個(gè)字符打頭的排列，然后把他們并起來(lái)燥撞，結(jié)果就是str的所有字符排列的可能性。
比如：string str = "abc"; 那么子問(wèn)題分別是:
{以a開(kāi)頭的排列集合} ∪ {以b開(kāi)頭的集合} ∪ {以c開(kāi)頭的集合}.
遞歸求解子問(wèn)題
分兩種情況：
- 字符串長(zhǎng)度為1迷帜，那么排列為自身物舒，這是遞歸的出口。
- 字符串長(zhǎng)度大于1戏锹，循環(huán)考慮str中每一個(gè)字符開(kāi)頭的情況冠胯。每一次循環(huán)，假如開(kāi)頭為某一字符锦针，后面得追加上剩余長(zhǎng)度為size -1的字符串的各種排列【調(diào)用函數(shù)本身】即可荠察。
例如：abc, 需要分別考慮將a，b , c 打頭的情況奈搜，對(duì)于以b打頭：
- b開(kāi)頭 追加上剩余部分：ac字符串的全排列悉盆，最終得到 bac, bca。
- 而ac字符串的全排列是通過(guò)遞歸調(diào)用函數(shù)本身得到的馋吗，即考慮ac中以a打頭和以c打頭的并集焕盟。
不重復(fù)
我這里打頭字符是通過(guò)循環(huán)和swap函數(shù)結(jié)合使用實(shí)現(xiàn)的。
當(dāng)我們swap的時(shí)候宏粤，與開(kāi)頭字母swap的字符可能與開(kāi)頭字符相同脚翘，這種情況下即使swap了灼卢，剩余部分的計(jì)算結(jié)果一定與前面重復(fù)。同理来农，當(dāng)我們已經(jīng)考慮過(guò)某一字符打頭的情況時(shí)鞋真，就不需要在后面的遍歷中，再次swap它到前面來(lái)沃于。
方法：維護(hù)一個(gè)記憶表涩咖，保存已經(jīng)考慮過(guò)的開(kāi)頭字符，每次swap前揽涮，都檢查是否計(jì)算過(guò).
代碼以及注釋
// 需要包含抠藕，<vector>,<string>,<iostream>等STL標(biāo)準(zhǔn)庫(kù)。
vector<string> permutation(string str) {
if (str.size() == 1)
return { str };
else {
vector<string> re; //存儲(chǔ)各種排列
//原字母開(kāi)頭的
//遞歸調(diào)用蒋困，返回字串的各種排列
vector<string> sub_pt = permutation(str.substr(1));
for (int i = 0; i < sub_pt.size(); ++i) {
//原首字母與剩余子串各種排列的組合盾似，加入返回列表
re.push_back(str.at(0) + sub_pt.at(i));
}
//通過(guò)交換使得身后其它字母開(kāi)頭
vector<char> save; //記錄不必再交換的
save.push_back(str.at(0)); //與首字母相同自然不用交換
for (int i = 1; i < str.size(); ++i) {
if (find(save.begin(), save.end(), str.at(i)) != save.end())
continue; //如果該字符已經(jīng)考慮過(guò)了，則跳過(guò)
string temp = str;
save.push_back(temp.at(i));//將該字符加入記憶表
swap(temp.at(0), temp.at(i));
vector<string> sub_pt = permutation(temp.substr(1));//遞歸調(diào)用
for (int i = 0; i < sub_pt.size(); ++i) {
//新首字母與剩余子串各種排列的組合雪标，加入返回列表
re.push_back(temp.at(0) + sub_pt.at(i));
}
}
return re;
}
