首页 > 代码库 > 算法：字符串的排列

算法：字符串的排列

2024-08-19 02:32:19   220人阅读

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

写了两种版本，一种为递归，一种为使用stl next_permutation 函数；
 1 class Solution {
 2 public:
 3     void all(vector<string> &v,string s,string str){
 4         if(str.size()==0){
 5             v.push_back(s);
 6             return;
 7         }
 8         for(int i =0;i!=str.size();++i){      
 9               //定义a因为不能改变当前层次的s
10             string a;
11             a+=str[i];
12             string tmp = str;
13             str.erase(str.begin()+i);
14             all(v,s+a,str);
15             str = tmp;
16         }
17     }
18     vector<string> Permutation(string str) {
19         vector<string> v;
20         if(str.size()==0)    return v;
21         string s;
22         all(v,s,str);
23         sort(v.begin(),v.end());
24         auto it = unique(v.begin(),v.end());   //去重
25         v.erase(it,v.end());
26         return v;
27     }
28 };
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> v;
        if(str.size()==0)    return v;
        if(str.size()==1){
            v.push_back(str);
            return v;
        }
        sort(str.begin(),str.end());
        do{
            v.push_back(str);
        }while(next_permutation(str.begin(),str.end()));
        return v;
    }
};

 



算法：字符串的排列


联系
我们