剑指offer编程题—字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路
递归算法
算法思想：固定第一位字符，求剩余字符的排列

1. 首先确定递归出口；
2. 遍历出所有可能出现在第一个位置的字符；
3. 固定第一个字符，递归求剩余字符的排列；
4. 递归返回后，将交换的两个字符复位，保证原始字符串中的第一个字符可以同后面所有的字符进行依次交换。

代码实现：
方案2和3是使用的字典序算法，详情参见上一篇字典序算法笔记

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

//递归算法
/*算法思想：固定第一位字符，求剩余字符的排列
1. 首先确定递归出口
2. 遍历出所有可能出现在第一个位置的字符
3. 固定第一个字符，递归求剩余字符的排列
4. 递归返回后，将交换的两个字符复位，保证原始字符串中的第一个字符可以同后面所有的字符进行交换
*/
class Solution {
public:
    vector<string> Permutation(string str) {
        if(str.length()<1) return vector<string>();
        //用set可以保证不会有重复排列，并且set内的记录会按照字典序自动排序
        set<string> result;
        Backtrack(0,str,result);
        vector<string> res(result.begin(),result.end());
        return res;
    }
    void Backtrack(int start,string &str,set<string> &res){
        if(str.length()-1==start){ //递归结束条件
            res.insert(str);
        }
        else{
            for(int i=start;i<str.length();++i){
                //避免重复交换，如果当前位置字符等于第一个字符，则不用与第一个字符交换
                if(i!=start && str[i]==str[start]) continue;
                //遍历出所有可能出现在第一位的字符
                //本质上是将第一个字符同后面所有的字符依次交换
                swap(str[start],str[i]); 
                //固定第一个字符，递归求剩余字符的排列
                Backtrack(start+1,str,res);
                //复位，保证for循环中第一个交换函数中实现的是第一个字符同其他字符的交换
                swap(str[start],str[i]);
            }
        }
    }
};

//字典排序算法
class Solution2 {
public:
    vector<string> Permutation(string str) {
        vector<string> result;
        if(str.length()<1) return result;
        sort(str.begin(),str.end());
        result.push_back(str);
        int len=str.length()-1;
        int i,j,k;
        while(true){
            for(i=len-1;i>=0 && str[i]>=str[i+1];--i) ;
            if(i<0) break;
            for(j=len;j>i && str[j]<=str[i];--j) ;
            swap(str[i],str[j]);
            reverse(str.begin()+i+1,str.end());
            result.push_back(str);
        }
        return result;
    }
};

//STL中调用next_permutation()函数求当前排列的基于字典序的下一个排列
class Solution3 {
public:
    vector<string> Permutation(string str) {
        vector<string> result;
        if(str.length()<1) return result;
        sort(str.begin(),str.end());
        result.push_back(str);
        while(next_permutation(str.begin(),str.end())) result.push_back(str);
        return result;
    }
};

void display(vector<string> v)
{
    for(int i=0;i<v.size();++i){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

int main(int argc,char **argv)
{
    string s="abc";
    Solution sol;
    vector<string> result=sol.Permutation(s);
    display(result);
    return 0;
}