输入一个 字符串 ,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例
- 输入:s = “abc”
- 输出:[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
限制
- 1 <= s 的长度 <= 8
方法:回溯法
dfs方法:
- 如果是最后一位,说明是最后一种排列,转化为字符串加入到结果中;
- 创建一个 HashSet 集合用于排除重复的值;
- 如果 固定的值 存在 set 集合中,代表其是重复字符,不作处理,直接跳过;
- 否则将 固定的值 加入到 set 集合中,之后用做去重处理;
- 将 固定的值 和 当前值 交换;
- 开始递归遍历 下一个值;
- 递归完毕后,还原之前的值。
permutation方法:
- 把字符串转化为 字符数组 ;
- 进行递归遍历;
- 返回结果字符串数组。
代码如下:
复杂度分析
- 时间复杂度: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
只要功夫深,铁杵磨成针,赠友人。
好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。