题目描述

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

解法

图片 按照该图的思路，排列可以将字符串分成两部分，第一部分为第一个字符，第二部分为除第一个字符之后的所有字符；固定第一位字符，然后求出后面字符可能出现的所有排列情况；求出后将第一位字符与后面的字符交换（更换第一位字符），然后再求出当前第一位字符情况下的所有排列；后面字符的求法也是固定第一位字符，然后求余下字符的可能排列，是个递归过程；

代码

class Solution {
public:
    vector<string> sortVec;
    vector<string> Permutation(string str) {
        if (str.length()==0) return sortVec;
        permutation(str,0);
        sort(sortVec.begin(), sortVec.end());
        return sortVec;
    }
    void permutation(string str, int begin) {
        if (begin >= str.length()) {
            string newSort = str;
            sortVec.push_back(newSort);
            return;
        }
        for (int i = begin; i < str.length(); i++) {
            if (str[i] == str[begin] && i!=begin) continue;

            char temp = str[i];
            str[i] = str[begin];
            str[begin] = temp;

            permutation(str, begin + 1);

            temp = str[i];
            str[i] = str[begin];
            str[begin] = temp;
        }
    }
};