剑指offer二十七--

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

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

<2.1.1>思路</h2>

先简化问题假设这n个字符不重复

大问题 n个字符全排列 =》让n个字符依次做第一个字符，每次固定后 + 后n-1个字符全排列

举例：abc排列 =》固定a bc排列、固定b ac排列、固定c ba排列

基线条件（递归结束条件): n个字符都排好了

递归条件（递归继续条件): 排好的字符个数小于n

递归体： for(int i = start;i++;i<=n){ 1.固定start 2.递归自身排后面的字符}

注：固定start，让n个字符依次做第一个字符，通过和第一个字符交换位置来实void Swap(char &a, char &b) {char tmp = a;

    a = b;
    b = tmp;
}

void PaiLie(char a[], int start, int len, vector<string> &result) {
    if (start == len - 1) {
        result.push_back(a);
        Display(a, len);
        return;
    }
    for (int i = start; i < len; i++) {
        Swap(a[start], a[i]);
        PaiLie(a, start + 1, len, result)；
        Swap(a[start], a[i]);  // 交换回去因为数组是引用传递，下面的递归交换顺序会影响上一层递归，所以每一层交换要交换回去

} }

然后进一步考虑重复字符的情况，按上面的思路处理，

例如 abb =》 1固定a 排bb 、2固定b 排b ab、3固定 b 排ba

aab =》 1固定a 排ab 2固定a 排 ab 3固定b 排aa

可见问题一：abb 2、3重复，其原因是a与相同元素交换了2次，

问题二：aab 1、2重复，原因是a与另一个a交换了，其后n-1个元素相同

综上，依次让n个字符做第一个字符，不能重复。

递归体做如下变换:

for(int i = start;i++;i<=n){ 1.只要出现过start位置就不再出现，通过一个set保证 2.递归自身排后面的字符}

<h3>2.1.2递归最终代码</h3>

#include<vector>
#include<string.h>
#include <iostream>
#include<algorithm>
#include<set>
using namespace std;
class Solution {
public:
  void Swap(char &a, char &b) {

    char tmp = a;
    a = b;
    b = tmp;
}

void PaiLie(char a[], int start, int len, vector<string> &result) {
    if (start == len - 1) {
        result.push_back(a);
        return;
    }
    set<char> is_apper;
    for (int i = start; i < len; i++) {
        if (is_apper.find(a[i]) == is_apper.end()) {// 如果从没有出现start位置，那就去走递归体
            is_apper.insert(a[i]); // 记录a[i]出现过start位置
            Swap(a[start], a[i]);
            PaiLie(a, start + 1, len, result);
            Swap(a[start], a[i]); // 恢复状态
        }
    }
}

vector<string> Permutation(string str) {
    vector<string> result;
    char *a = new char[str.size()];
    strcpy(a, str.c_str()); // 将string转为char
    PaiLie(a, 0, str.size(), result);
    sort(result.begin(), result.end());// 保证字典序，即result里的东西有序
    return result;
}
};

<h2>2.2动态规划解法</h2>