字符串的排列

题目描述

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

输入描述:

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

第一想法

大小写的相同字母构成的字符串是否算同一个?比如说AAc和aaC?
无重复的字母排列是n!(按字典序输出)
计算机中没有字典序就用ACSII码排序吧,但是aa和AA哪个排前面?
c++中的字符串如何使用
提示中有动态规划,那么问题来了,动态规划是什么?

我的想法

像之前找路径那样的想法我已经想到了。在Vsc里面写了一些。

    void CA(string str){
        if(str.length() == 0){
            return ;
        }
        if(str.length() == 1){
            cstr.push_back(str[0]);
            fstr.push_back(cstr);
        }
        for(int i = 0; i < str.length(); ++i){
            cstr.push_back(str[i]);
            CA(delete_char(str,str[i]));
            cstr.pop_back();
        }
        return ;
    }

就像那棵树一样,只不过一个是左右子树的push与pop,这个是有好多子树来for()

问题在于我选择的是新建空间,比如说{A,B,C}
A -> vec
然后要把A删掉的BC字符串放进去,写删除str中char的函数的时候出现了一些些问题,就看讨论区有没有更简易的办法.

看了讨论区

本来以为要自己手动实现sort函数,结果你告诉我可以直接调用???我懵了.

这是递归回溯法的解法.只是它是用的swap,我是新建再放进去的办法

class Solution {
public:
    vector<string> result;
    vector<string> Permutation(string str) {
        if(str.length() == 0)
            return result;
        Permutation(str, 0);
        //保证是字典序
        sort(result.begin(), result.end());
        return result;
    }
    void Permutation(string str, int begin){
        if(begin == str.length() - 1){
            result.push_back(str);
            return ;
        }
        for(int i = begin; str[i] != '\0';i++){
            //begin != i;因为首个交换的即是它本身，必定相等。
            //我们要找出之后相等的，跳过（重复的就不用交换了）。
            if(begin != i && str[i] == str[begin])
                continue;
            swap(str[i],str[begin]);
            Permutation(str,begin + 1);
            //因为在这个for中,是同一层的.之前交换过去的begin头还要交换回来
            //首元素,譬如说A,与B交换之后要交换回来再和C交换
            swap(str[i],str[begin]);
        }
    }
};

字典序全排列博客
https://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html

以下是实现代码

class Solution {
public:
    /*
    设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
  1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}
  2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）
  3）对换pj，pk
  4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。
  */
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        int len = str.length();
        if(len == 0)
            return res;
        else if(len == 1){
            res.push_back(str);
            return res;
        }
        str = sortStr(str);
        res.push_back(str);
        int left = -1, right = len - 1;
        while(true){
            left = -1;
            for(int i = len - 1; i > 0; --i){
                if(str[i - 1] < str[i]){
                    left = i - 1;
                    break;
                }
            }
            if(left == -1)
                break;
            for(int j = left + 1; j < len; ++j){
                if(str[j] > str[left])
                    right = j;
            }
            swap(str[left], str[right]);
            for(int i = left + 1,j = len - 1; i < j; i++,j--){
                swap(str[i], str[j]);
            }
            res.push_back(str);
        }
        return res;
    }

    string sortStr(string str){
        int len = str.length();
        char tmp;
        for(int i = 0; i < len - 1; ++i)
            for(int j = 0;j < len - 1 - i; ++j)
                if(str[j] > str[j + 1]){
                    tmp = str[j];
                    str[j] = str[j + 1];
                    str[j + 1] = tmp;
                }
        return str;
    }
};

字典排序

从小到大排序
从后往前,找到后面那个大于前面那个的位置,前面的下标为left,
从left + 1开始向后找,找到最后一个大于left位置的下标为right
交换left / right 的值,
将 left后的序列逆序.
得到的就是字典序列中原序列后一个序列.

eg.
12398745 ---- 45 然后变成12398754

12398754 ---3和9
找到 4交换 12498753
reverse 98753 是35789
12398754的后一个即为 12435789