算法进阶——字符串的排列

题目

---

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10

要求：空间复杂度 O(n!)，时间复杂度 O(n!)

输入描述：输入一个字符串,长度不超过10,字符只包括大小写字母。

示例1

输入：
"ab"
返回值：
["ab","ba"]
说明：
返回["ba","ab"]也是正确的
1
2
3
4
5
6

示例2

输入：
"aab"
返回值：
["aab","aba","baa"]
1
2
3
4

示例3

输入：
"abc"
返回值：
["abc","acb","bac","bca","cab","cba"]
1
2
3
4

示例4

输入：
""
返回值：
[""]
1
2
3
4

思路

---

使用递归的思路，每次先交换一个字符（可以是自己），然后将这个字符固定，之后递归的将后面的字符进行一次全排列，最后记得每次递归完需要回溯，也就是将交换的字符还原。

另外原字符串中可能存在重复的字符，如“aab”，经过递归后会有重复的，所以可以使用set来保存结果，以达到去重的效果。

递归三件套：

• 递归函数的功能：Permutation(int pos, string str), 表示固定字符串str的pos下标的字符str[pos]
• 递归终止条件：当pos+1 == str.length()的时候，终止。完成了一次全排列。
• 下一次递归：Permutation(pos+1, str), 很显然，下一次递归就是对字符串的下一个下标进行固定。

解答代码

---

#include 
#include 
#include 
class Solution {
public:
    /**
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        // write code here
        vector<string> ret{""};
        if (str.empty()) {
           return ret; 
        }

        //用set去重
        set<string> no_repeat_ret;
        Permutation(0, str, no_repeat_ret);
        ret.assign(no_repeat_ret.begin(), no_repeat_ret.end());
        return ret;
    }

    void Permutation(int pos, string str, set<string>& no_repeat_ret) {
        if (pos+1 == str.length()) {
            // 递归终止条件：完成一次全排列
            no_repeat_ret.emplace(str);
            return;
        }

        for (int i = pos; i < str.length(); i++) {
            // 交换字符，固定一个字符
            swap(str[pos], str[i]);
            // 递归调用，对字符串的下一个下标进行固定
            Permutation(pos+1, str, no_repeat_ret);
            // 递归完需要回溯
            swap(str[pos], str[i]);
        }
    }
};
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
28
29
30
31
32
33
34
35
36
37
38
39
40