字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路
- 递归思想：把大问题转换为若干小问题；
- n个元素的全排列 = （n-1） 个元素全排列 + 一个元素作为前缀。
- 递归的出口：只有一个元素的全排列，此时排序完成，输出数组。
- 遍历字符串，将每个字符放在第一个元素作为前缀，并将其余元素继续全排列。
- 新建一个isRepeat空对象，用来判断字符是否重复，若重复则跳过排序。
实现代码
function Permutation(str) {
var result = [];
if (str.length <= 0) {
return [];
}
var sortTemp= "";
var arr = str.split("");
result = sortString(arr, sortTemp, []);
return result;
}
function sortString(arr, sortTemp, res) {
if (arr.length == 0) {
res.push(sortTemp);
} else {
var isRepeat = {};
for (var i = 0; i < arr.length; i++) {
if (!isRepeat[arr[i]]) {
var temp = arr.splice(i, 1)[0]; // 取出第i个字符
sortTemp+= temp; // 第i个字符设为前缀
sortString(arr, sortTemp, res);
arr.splice(i, 0, temp); // 补全取出的元素，恢复原字符串
sortTemp= sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp
isRepeat[temp] = true;
}
}
}
return res;
}
