JZ27 字符串的排列

题意分析

将字符串中的字符进行排列组合，生成所有的字符串。

示例输入：input = "ab"
返回：["ab","ba"]
解释：字符a和b可以排列组合生成ab和ba。

题解一（暴力回溯）：

回想一下高中所学的排列组合知识：有3个红球，2个白球，1个黑球，请问有多少中排列方式。

我们的计算方式是：一个有6个位置，先选择3个位置放红球，再从剩下的3个位置中选择2个位置放白球，最后剩下一个位置放黑球。总共的排列数有种。

我们这题就是要用代码生成这些排列。

我们从左往右依次填入给定的字符，每个字符使用一次。

当我们使用完了所有的字符，那么就可以将生成的字符串加入到最终结果中。
当我们没有使用完字符，考虑下一步应该使用什么字符呢？之前使用过的字符不能再使用了。我们可以对使用过的字符做一个标记，表示已经使用过了。然后使用没有标记过的字符。

依据之前提到放球的解答，我们应该把不同的字符做一个统计，然后把他们放到一些位置中。我们使用map<char,int>m给不同的字符做标记。如果字符i使用了一次。m[i]--。相应的当m[i]==0时，表示没有字符i可供使用。

算法实现如下：

void backtrack(map<char, int> &m, vector<string> &ret, string &tmp, int n) {
    if (tmp.size() == n) {
        ret.push_back(tmp);//当最后生成的tmp string长度等于n即可添加到最后结果中，n指的是输入字符串长度，
    }
    for (auto &i:m) {
        if (i.second > 0) {//当i.second>0,表示有字符i.first可以被使用
            i.second--;//使用一次字符i.first,i.second--;
            tmp += i.first;//加到生成的字符串中
            backtrack(m, ret, tmp, n);//下一步生成tmp
             tmp.pop_back();
            i.second++;//上面回溯结束后，使用过的i.first拿出去，又可以被使用，因此tmp弹出最后一个元素，i.second++
        }
    }
}

vector<string> Permutation(string &S) {
    map<char, int> m;
    for (char & i : S) {
        m[i]++;
    }
    vector<string> ret;
    string tmp;
    backtrack(m, ret, tmp, S.size());
    return ret;
}

时间复杂度：与字符串中字符的种类有关。非确界上界为。

空间复杂度：。我们需要 栈空间进行回溯。

题解二(取巧）：

C++有个叫next_permutation函数。可以参考[官方文档](next_permutation - C++ Reference (cplusplus.com))，了解去功能和用法。简单的来说他可以帮忙生成下一个排列。因此我们不断的使用这个函数求下一个排列即可。

vector<string> Permutation(string &s) {
    sort(s.begin(), s.end());
    vector<string>ret;
    ret.push_back(s);
    while(next_permutation(s.begin(), s.end())){
        ret.emplace_back(s);
    };

    return ret;
}

题解三（自己实现一个next_permutation）:

bool next_Permutation_Of_Own(string& s) {
    int i = s.size() - 2;
    while (i >= 0 && s[i] >= s[i + 1]) {
        i--;
    }
    if (i < 0) {
        return false;
    }
    int j = s.size() - 1;
    while (j >= 0 && s[i] >= s[j]) {
        j--;
    }
    swap(s[i], s[j]);
    reverse(s.begin() + i + 1, s.end());
    return true;
}

用 nextPermutation_of_Own(string& s)代替内置的next_permutation。

时间复杂度：。

空间复杂度：。仅仅在sawp时候用到额外的一个变量。