字符串的排列

作者: cherryleechen | 来源:发表于2019-05-06 21:25 被阅读0次

    时间限制:1秒 空间限制:32768K

    题目描述

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

    输入描述:

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

    我的代码

    class Solution {
    public:
        vector<string> Permutation(string str) {
            vector<string> res;
            if(str.size()<1 || str.size()>9)
                return res;
            sort(str.begin(),str.end());
            res.push_back(str);
    /*next_permutation基本思想,将序列分成3部分,第一部分保持不变,
    第二部分只有一个数字并且要与第三部分中某个数字进行交换,交换后第三部分进行逆序排列。
    从右往左找出第一对相邻递增对,对中前者即为第二部分。
    在第三部分中从右往左找出第一个大于第二部分的数字,与第二部分进行交换后,将第三部分逆序。*/
            while(next_permutation(str.begin(),str.end())){
                res.push_back(str);
            }
            return res;
        }
    };
    

    运行时间:4ms
    占用内存:472k

    class Solution {
    public:
        vector<string> Permutation(string str) {
            //对于a,b,c,交换a,b后,固定b,求a,c排列,交换回a,b;
            //交换a,c后,固定c,求a,b排列,交换回a,c。
            vector<string> res;
            if(str.size()<1 || str.size()>9)
                return res;
            change(res,str,0);
            sort(res.begin(),res.end());
            vector<string>::iterator it=unique(res.begin(),res.end());
            res.resize(distance(res.begin(),it));
            //res.erase(it,res.end());
            return res;
        }
        void swap(char &a, char &b){
            char tmp=a;
            a=b;
            b=tmp;
        }
        void change(vector<string> &res, string str, int begin){
            if(begin==str.size()-1)
                res.push_back(str);
            for(int i=begin;i<str.size();i++){
                swap(str[begin],str[i]);
                change(res,str,begin+1);
                swap(str[begin],str[i]);
            }
        }
    };
    

    运行时间:4ms
    占用内存:492k

    相关文章

      网友评论

        本文标题:字符串的排列

        本文链接:https://www.haomeiwen.com/subject/aijtoqtx.html