【剑指offer】字符的全排列
程序员文章站
2024-03-22 14:57:16
...
????题目
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
输入:s = “abc”
输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
☘️解析
显然,这是一个「全排列」问题。
全排列的模板(即swap交换法)不再赘述,本题的关键在于「去重」。
去重思路一:所有可能的排列结果(字符串)都存到Set集合中,让容器帮我们完成去重的操作。
去重思路二:每一次swap的本质是固定一次index处的字符,那么如果每种字符只在index处固定一次,就可以保证去重。
????代码
全排列模板+去重思路一:
class Solution {
public String[] permutation(String s) {
DFS(s.toCharArray(), 0);
return res.toArray(new String[res.size()]);
}
private Set<String> res = new HashSet<>();
private void DFS(char[] arr, int index) {
if (index == arr.length) {
res.add(new String(arr));
return;
}
for (int i = index; i < arr.length; i++) {
char temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
DFS(arr, index + 1);
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
全排列模板+去重思路二:
class Solution {
public String[] permutation(String s) {
DFS(s.toCharArray(), 0);
return res.toArray(new String[res.size()]);
}
private List<String> res = new ArrayList<>();
private void DFS(char[] arr, int index) {
if (index == arr.length) {
res.add(new String(arr));
return;
}
Set<Character> set = new HashSet<>();
for (int i = index; i < arr.length; i++) {
if (set.contains(arr[i])) {
continue;
}
set.add(arr[i]);
char temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
DFS(arr, index + 1);
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
????补充
1)算法课上多次强调,全排列的时间复杂度是 O(n * n!)。
2)做一个区分:全排列问题使用的是swap模板,这有别于一般的回溯模板。这是因为全排列问题可以改变元素之间的相对顺序。
推荐阅读
-
剑指offer 全排列 题
-
【剑指offer】字符的全排列
-
剑指 Offer 04. 二维数组中的查找 专注技术的小飞
-
【刷题库】剑指Offer_编程题第16题(JavaScript实现),合并两个排序的链表。
-
剑指offer(牛客)---36.数字在排序数组中出现的次数
-
剑指offer | 数字在排序数组中出现的次数
-
数字在排序数组中出现的次数(二分查找法)——剑指Offer
-
剑指offer:数字在排序数组中出现的次数(二分查找 leetcode 34)
-
剑指offer-37-数字在排序数组中出现的次数(二分查找) -- Java实现
-
剑指offer——数字在排序数组中出现的次数(复习二分)