算法：字符串的排列

迈不过友情╰ 2024-04-03 11:17 33阅读 0赞

![878f282c5ef3bbdfd90e35355717a03c.jpeg][]

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

## 示例 ##

*  输入：s = "abc"
 *  输出：\["abc","acb","bac","bca","cab","cba"\]

## 限制 ##

*  1 <= s 的长度 <= 8

## 方法：回溯法 ##

**dfs方法：**

*  如果是最后一位，说明是最后一种排列，转化为字符串加入到结果中；
 *  创建一个 HashSet 集合用于排除重复的值；
 *  如果 固定的值 存在 set 集合中，代表其是重复字符，不作处理，直接跳过；
 *  否则将 固定的值 加入到 set 集合中，之后用做去重处理；
 *  将 固定的值 和 当前值 交换；
 *  开始递归遍历 下一个值；
 *  递归完毕后，还原之前的值。

**permutation方法：**

*  把字符串转化为字符数组；
 *  进行递归遍历；
 *  返回结果字符串数组。

**代码如下：**

![f1a743c09721c241fd9ceb5503a9bb27.jpeg][]

## 复杂度分析 ##

*  时间复杂度：O(N!N)，N 为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 N×(N−1)×(N−2)…×2×1 ，即复杂度为 O(N!) ；字符串拼接操作 join() 使用 O(N) ；因此总体时间复杂度为 O(N!N) 。
 *  空间复杂度 ：O(N的2次方) ，全排列的递归深度为 N ，系统累计使用栈空间大小为 O(N) ；递归中辅助 Set 累计存储的字符数量最多为 N+(N−1)+...+2+1=(N+1)N/2 ，即占用 O(N的2次方) 的额外空间。

## END ##

只要功夫深，铁杵磨成针，赠友人。

[878f282c5ef3bbdfd90e35355717a03c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c57368031a9e40a9a7b6e8a31f6496e4.jpeg
[f1a743c09721c241fd9ceb5503a9bb27.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1a794c858b184aeeb5be8fdc93a50e7d.jpeg