字符串的排列

题目描述

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

输入描述:

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

解题思路

class Solution {
public:
    //回溯法
    vector<string> Permutation(string str) {
        vector<string> result;
        //空字符串直接返回result
        if(str.size()==0)
            return result;

        //用一个集合进行存储，避免重复，同时默认排好序了
        set<string> res;
        Permutation(str,res,0);
        //将集合中的元素依次加入result
        for(auto &e:res)
            result.push_back(e);
        return result;
    }

    void Permutation(string str, set<string>& res, int begin)
    {
        //递归结束条件：索引已经指向str最后一个元素时
        if(begin==str.size()-1)
            res.insert(str);
        else
        {
            for(int i=begin;i<str.size();i++)
            {
                //依次进行交换
                swap(str[begin],str[i]);
                Permutation(str,res,begin+1);
                //复位
                swap(str[begin],str[i]);
            }
        }
    }

    //交换两个字符
    void swap(char& first,char& second)
    {
        char t = first;
        first = second;
        second = t;
    }
};