字符串的排列

题目描述

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

问题分析

首先，我们把一个字符串看成两部分组成：第一部分为它的第一个字符，第二部分为后面的所有字符。首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面的所有字符的排列。这个时候我们仍然把后面所有的字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符，然后把第一个字符逐一和它后面的字符交换。

解题思路1

class Solution {
public:
    vector<string> Permutation(string str) {
        int len = str.length();
        vector<string> str_print;
        if (str.empty())
        {
            return str_print;
        }
        int start_id = 0;
        Permutation_iter(str, 0, str_print);
        sort(str_print.begin(),str_print.end());
        return str_print;

    }
    
    void Permutation_iter(string str, int start_id, vector<string> &str_print)
    {
        int len = str.size();
        //not end
        if (start_id == str.size()-1)
        {
            if (find(str_print.begin(), str_print.end(), str) == str_print.end())
            {
                str_print.push_back(str);
            }
        }
        else
        {
            for (int i = start_id ; i <str.size(); i++)
            {
                //swap
                swap(str[start_id], str[i]);
                //str_print.push_back(str);
                Permutation_iter(str, start_id+1, str_print);
                //reset
                swap(str[start_id], str[i]);

            }
            
        }

    }
    void swap(char &first, char & second)
    {
        char tmp = first;
        first = second;
        second = tmp;
    }
};