字符串的排列

题目描述

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

输入描述：

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路：递归，字符交换
如 abc,第0个字符串和第0个开始到最后一个字符交换，得到 abc,bac,cab。递归 bc->bc cb，...

class Solution {
public:
    vector<string> Permutation(string str) {
     vector<string>vec;
        if (str.size() == 0) {
            return vec;
        }
        getString(str, 0, vec);
        /*
        如果不排序，输出结果有错
        正确结果：["abc","acb","bac","bca","cab","cba"]
        输出结果：["abc","acb","bac","bca","cba","cab"]
        */
        sort(vec.begin(), vec.end());
        return vec;
    }
    //遍历字符串
    void getString(string &str, int low,vector<string> &vec) {
        int high = str.size() - 1;
        if (low >= high) {
            vec.push_back(str);
            return;
        }
        else {
            for (int i = low; i <= high; i++)
            {
                //如果相邻字符相同则不重复遍历。如aab
                if (low == i || str[i] != str[low]) {
                    //字符交换
                    swap(str, i, low);
                    getString(str, low + 1,vec);
                    swap(str, low, i);

                }
            }
        }
    }
    void swap(string &s, int start, int end) {
        char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
    }

};