[41]字符串的排列-美丽联合2018秋

1.题目描述

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

• 输入描述:
  输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母,例如 ac
• 输出描述:

  [ac, ca]
  

• 输入示例:

  acc
  

• 输出示例:

  [acc, cac, cca]
  

2.题目解析

老大轮流做

分析abc的全排列

分析acc的全排列(相当于把abc中的b换成c)

回溯法

3.参考答案

1. 使用set解决重复和排序问题。

class Solution {
public:
    void Permutation(set<string>& res, string & s, size_t start) {
    if(start == s.length()) {
        res.insert(s);
        return;
    }
    // 从位置k往后，重新排列
    for(size_t i = start; i < s.length(); i++) {
        swap(s[start], s[i]);// 交换位置
        Permutation(res,s, start+1);
        swap(s[start], s[i]);// 还原交换位置
    }
    }
    vector<string> Permutation(string str) {
        if(str.empty()) return vector<string>();
        set<string> res;
        Permutation(res,str,0);
        return vector<string>(res.begin(),res.end());// 把set转成vector
    }
};

2. 使用vector手动解决重复和排序问题。

class Solution {
public:
    void Permutation(vector<string> &res, string &s, size_t start) {
    if(start == s.length()) {
        res.push_back(s);
        return;
    }
    // 从位置k往后，重新排列
    for(size_t i = start; i < s.length(); i++) {
        if (i != start && s[start] == s[i]) // 重复字符不处理
          continue;
        swap(s[start], s[i]);// 交换位置
        Permutation(res,s, start+1);
        swap(s[start], s[i]);// 还原交换位置
    }
    }
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty()) return res;
        Permutation(res,str,0);
        sort(res.begin(),res.end()); // 排序
        return res;
    }
};

3. 使用STLnext_permutation()

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty()) return res;
        do {
            res.push_back(str);
        } while(next_permutation(str.begin(), str.end()));
        return res;
    }
};

• 牛客题目