問題
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
遞歸
思路：從字符串中選出一個字符作為排列的第一個字符，然后對剩余的字符進(jìn)行全排列。如此遞歸處理，從而得到所有字符的全排列。
分析：我們可以先根據(jù)一個實際的例子想想，怎樣才能無遺漏的輸出全排列：
兩個數(shù)就不用說了，對于 ab，只有 ab 和 ba 兩種
三個數(shù)，比如 abc，我們先分為三種情況，就是 a 開頭，b 開頭和 c 開頭
對于 a 開頭的情況，剩下 b 和 c，這就回到了兩個數(shù)的排列；
對于 b 開頭的情況，剩下 a 和 c，這也回到了兩個數(shù)的排列；
c 開頭的情況同理；
四個數(shù)，先按照開頭分為四種情況，然后按照三個數(shù)的排列去處理
……
以此類推
由此可看出，這是一個遞歸。就好像求斐波那契數(shù)列的某一個元素，我們要先求出前面的；要想求出前面的，我們就要求出更前面的。記 “斐波那契數(shù)列的第 n 位” 這件事為 F(n)，則有 F(n) = F(n - 1) + F(n - 2)。
類似地，記 “求出 n 個字符串的全排列” 這件事為 P(n)，則有P(n) = 分別以這n個字符之一開頭 + P(n - 1)。其中，P(n - 1) 表示去掉那個開頭字符的剩余字符串的全排列。哪怕只有兩個字符，比如對于上面例子中的 ab，同樣符合這一條結(jié)論。
- 分析：以 'abc' 為例，執(zhí)行步驟如下：
- a 作為開頭 -> 求 bc 全排列 -> 得到 bc 和 cb -> 與 a 合并 -> 得到 abc 和 acb
- b 作為開頭 -> 求 ac 全排列 -> 得到 ac 和 ca -> 與 b 合并 -> 得到 bac 和 bca
- c 作為開頭 -> 求 ab 全排列 -> 得到 ab 和 ba -> 與 c 合并 -> 得到 cab 和 cba
注：之前遞歸過程選擇的字符，下一次不能再被選。
時間復(fù)雜度：O(n！)。
function permutation(str) {
if(str.length == 0) {
return [];
}
var result = [];
var sortTemp = '';
var arr = str.split('');
// var len = arr.length;
var result = sortString(arr, sortTemp, result);
return result;
function sortString(arr, sortTemp, res) {
if(arr.length == 0) {
return res.push(sortTemp);
} else {
let isRepeat = {};
for(let i = 0; i < arr.length; i++) { // 不要用 len
if(!isRepeat[arr[i]]) {
let temp = arr.splice(i, 1)[0]; // i 取出第i個字符作為第一個字符
sortTemp += temp;
sortString(arr, sortTemp, res); // 固定第一個字符的剩下字符的全排列已完成
arr.splice(i, 0, temp); // i 補全 恢復(fù)原字符串
sortTemp = sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp: 每次截掉字符串中的最后一個字符
isRepeat[temp] = true; // 相同的字符便不再在第一個字符中固定并對剩下的字符進(jìn)行全排列了
}
}
}
return res;
}
}
permutation('abc')
這里固定字符串?dāng)?shù)組元素中的第一個字符的方式：是利用數(shù)組中splice()方法通過截取出來（刪掉一個元素），完成全排列后再將該字符補全回原字符串中splice()（添加元素）的方式。遍歷該字符串?dāng)?shù)組，依次截取掉每個字符元素的方式來作為字符串?dāng)?shù)組元素的第一個字符。
當(dāng)然還可以通過依次向后交換的方式、或者取出元素以后向后插入的方式、以及經(jīng)典的回溯法的方式等等。
