字符串的排序

---

题目描述

输入一个字符串，按字典序打印出该字符串中字符的所有排列，列如输入字符串abc，则打印出所有排列出来的所有字符串abc，acb，bac，bca，cab，cba。

输入描述：输入一个字符串，长度不超过9（可能有字符重复），字符只包括大小写字母。

解题思路

字典序：字典序不仅仅是比较英文字母，而是比较任意字符串。对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的ASCLL值得大小关系。

可以考虑回溯排序的方法，方法示例如下：

首先遍历所有字符，因为这些字符都会出现在第一个位置上进行固定。（即需要与第一个位置的字符交换）

然后，固定第一个字符，然后对后面的字符进行排列（即，通过递归的方法对剩余字符进行上述排列）

代码

class Solution
{
public:
    void Sort(string str, int begin)
    {
        if (str.length() == begin) // 递归结束的条件
        {
            result.push_back(str);
            return;
        }
        
        for (int i = begin; i < str.length(); i++)
        {
            if (i != begin && str[begin]==str[i]) // 若遍历后面的字符与第一个元素相等则跳过该字符
                continue;
            swap(str[begin], str[i]);
            Sort(str, begin+1);// 递归剩余的字符
        }
    }
    
    vector<string> Permutation(string str)
    {
        if (str.length() == 0)
            return result;
        
        Sort(str, 0);
        
        //排列完的结果，可能不是按照字典序排列的，需要重新排一下顺序
        sort(result.begin(), result.end());
        return result;
    }
private:
    vector<string> result;
};

---

参考链接：https://cuijiahua.com/blog/2017/12/basis_27.html

https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?f=discussion