JZ38 字符串的排列

发表于 分类于 本文字数： 605 阅读时长 ≈ 2 分钟

JZ38 字符串的排列

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

img

数据范围：$n<10$
要求：空间复杂度 $O(n!)$，时间复杂度 $O(n!)$

输入描述：

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

示例1

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

示例2

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

示例3

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

示例4

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

题解

初见思路：看到题目知识点中带了一个递归，就考虑用递归的方法来做。最后得到的方法是每往下一层减少一个尾部的字符，直到只剩一个字符为止则返回该字符，然后对返回的每一个结果，把减少的这个字符尝试插入到每一个位置里面，最后进行一次去重，结果AC了。

大G老师点评：复杂度没问题，和我考虑的一样，重复字符导致出现了很多不必要的枝，大G老师给出的方法是回溯+剪枝优化，用无序集合保存已经使用过的字符，然后每个结果是通过对调生成的，和我的插入生成的方式不一样。

代码

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
#include <string>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        if (str == "") return {""};
        if (str.length() == 1) return vector<string> {str};
        vector<string> ans;
        char lastChar = str.back();
        str.pop_back();
        for (string back_str : Permutation(str)) {
            for (int i = 0; i <= str.length(); i++) {
                string curr = back_str;
                curr.insert(i, 1, lastChar);
                ans.push_back(curr);
            }
        }

        vector<string> res;
        unordered_set<string> seen;

        for (const auto& s : ans) {
            if (seen.count(s) == 0) {
                res.push_back(s);
                seen.insert(s);
            }
        }
        return res;
    }
};

回溯+剪枝代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void backtrack(string &s, int start, vector<string> &res) {
    if (start == s.size() - 1) {
        res.push_back(s);
        return;
    }
    unordered_set<char> used;
    for (int i = start; i < s.size(); i++) {
        if (used.count(s[i])) continue; // 剪枝
        used.insert(s[i]);
        swap(s[start], s[i]);
        backtrack(s, start + 1, res);
        swap(s[start], s[i]);
    }
}

vector<string> Permutation(string str) {
    vector<string> res;
    if (str.empty()) return res;
    sort(str.begin(), str.end()); // 可选：生成字典序
    backtrack(str, 0, res);
    return res;
}