剑指offer27

剑指offer27：字符串的排列

题目描述

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

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

解法一：基于STL的next_permutation函数

class Solution {
public:
    vector<string> Permutation(string str) {
        if (str.empty())
            return {};
        sort(str.begin(), str.end());
        vector<string> answer;
        answer.push_back(str);
        //C++ STL标准库排列算法next_permutation函数
        while (next_permutation(str.begin(), str.end()))
            answer.push_back(str);
        return answer;
    }
};

解法二：基于递归和回溯的方法

class Solution2 {
public:
    void perm(int pos, string s, set<string> &ret) {
        if (pos + 1 == s.length()) {
            ret.insert(s);
            return;
        }
        // for循环和swap的含义：对于“ABC”，
        // 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
        // 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
        // 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
        for (int i = pos; i < s.length(); ++i) {
            swap(s[pos], s[i]);
            perm(pos + 1, s, ret);
            swap(s[pos], s[i]);
            // 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
            // 然后进行第三次交换，才能得到"CBA"
        }
    }
    vector<string> Permutation(string s) {
        if (s.empty()) return {};
        //set集合默认升序排序，且可以达到去重的效果
        set<string> ret;
        perm(0, s, ret);
        return vector<string>({ ret.begin(), ret.end() });
    }
};

main函数

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main()
{
    string str;
    cout << "请输入字符串str: " << endl;
    cin >> str;
    Solution2 answer;
    vector<string> b;
    b=answer.Permutation(str);
    cout << "字符串str的全排列为: " << endl;
    for (auto n : b)
        cout << n << endl;


    system("pause");
    return 0;
}