【剑指offer】字符串的排列

原创博文，转载请注明出处！

本题代码github地址

题目

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

思路（递归）

      分两步求字符串的全排列：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换；然后固定第一个字符，求后面所有字符的全排列。

代码

class Solution {
public:
    vector<string> Permutation(string str) 
    {
        // 存储结果
        vector<string> res;
        
        // 特殊输入
        if(!str.empty())
        {
            fun(res,str,0); // 全排列
            sort(res.begin(),res.end()); // 排序
        }
        return res;
    }
    // 递归
    void fun(vector<string> &res,string str,int begin)
    {
        // 最后一个元素
        if(begin==str.size()-1)
            res.push_back(str);
        else
            for(int i = begin;i<str.size();++i)
            {
                // 去重
                if(i!=begin && str[i] == str[begin]) continue;
                
                // 交换+递归+交换
                swap(str[i],str[begin]);
                fun(res,str,begin+1);
                swap(str[i],str[begin]);
            }
    }
};