字符串全排列

问题描述

策略选择

  • 循环构建全排列
  • 递归构建全排列
  • 判断相同字符的选择

算法设计

算法分析

  • 时间复杂度O(n!)
  • 空间复杂度O(n2)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<string> permutation(string s) {
    vector<string> vec;
    string pre;
    perm(pre,s,vec);
    return vec;
}

void perm(string pre,string s,vector<string> &vec){
    if(s.size()==0){
        // cout<<pre<<endl;
        vec.push_back(pre);
        return;
    }
    set<char> se;
    for(int i=0;i<s.size();i++){
        string temp = s;
        if(se.count(s[i])){
            continue;
        }
        else{
            se.insert(s[i]);
        }
        perm(pre+s[i],temp.erase(i,1),vec);
    }

    return ;
}