剑指offer：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：本题考查递归解决问题的思路。首先将输入的字符串转化为有序字符串。将字符串分为两部分，第一个字符，和后续N-1个字符。后续问题可以用递归函数。
按顺序确定第一个字符，然后递归操作剩下的N-1个字符（要保证后面N-1个字符为有序的）。有意思的是， for (int i = index; i < len; ++i) { if (i!=index && str[i]== str[index]) continue;// 保证当输入多个重复字符时，不会重复计算 swap(str[i],str[index]);//每一次，交换第i个位置和首位置的元素 Permutations(result, str, index+1, len); } 上面的操作居然能够保证后面是有序的，而不用调用排序程序。比如abcd 首先是a作为第一个字符，后续是bcd 。第二次，首位的a和b互换位置，变成，b acd显然acd有序
再接着，首位的b和c互换位置，得c abd 又是有序的。
代码如下：
class Solution { private: string temp; private: vector<string> result; public: vector<string> Permutation(string str) { vector<string> result; //创建字符串数组 int len = str.length(); //求出字符串长度，作为参数传递控制循环次数 if(!len) return result; //当输入为空时，直接返回 BubbleSort(str,0,len-1); Permutations(result, str, 0, len); return result; } void Permutations(vector<string>&result, string str,int index, int len){ //当索引指向字符串尾部时，将str压入数组 if (index == len){//index==len,说明首位置已经是末尾了，这时的递归输入已经只有一个元素了 result.push_back(str); return; } for (int i = index; i < len; ++i) { if (i!=index && str[i]== str[index]) continue;// 保证当输入多个重复字符时，不会重复计算 swap(str[i],str[index]);//每一次，交换第i个位置和首位置的元素 Permutations(result, str, index+1, len); } } void BubbleSort(string &A,int left,int high){ int p,i; bool flag; int N = A.length(); for(p=N-1; p >= 0; p--){ flag = false; for(i=0; i<p; i++){ if(A[i]>A[i+1]){ swap(A[i],A[i+1]); flag = true; } } if(flag == false) break; } } };
