题目:
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例:
输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]
限制:
1 <= s 的长度 <= 8
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
回溯步骤:回溯法一般是在集合中递归搜索,并抽象为树形结构,集合的大小为数的宽度,递归的深度构成数的深度。
1.回溯函数模板返回值以及参数,函数返回值一般为void。
2.回溯的终止条件;
3.回溯的搜素遍历过程;
思路:
- 初始化:temp:存放临时组合,result:存放结果,used:是否使用过,初始化为false, 将字符串转换为字符数组,并进行排序(未来后续判断相邻位置字符是否相同)
- 回溯函数:
- 当临时数组temp的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点,存放进result;
- 从头开始循环遍历字符数组
- 当前后两个字符相同 且 前一个字符已经使用过时,就跳过当前字符,继续for循环
- 如果当前元素未被使用过,先标记当前元素,然后将当前元素加入temp,再继续回溯下一层直到排列完成,再撤销选择回到未被标记状态。
代码:
1 class Solution { 2 List<String> result = new ArrayList<>(); 3 //暂存结果 4 StringBuffer temp = new StringBuffer(); 5 public String[] permutation(String s) { 6 //将字符串转换为字符串数组 7 char[] chars = s.toCharArray(); 8 //将字符数组进行排序 9 Arrays.sort(chars); 10 //定义一个boolean数组标记使用过的数组 11 boolean[] used = new boolean[chars.length]; 12 //初值全为未被使用 13 Arrays.fill(used, false); 14 //求出排列 15 backtracking(chars, used); 16 //返回结果 17 return result.toArray(new String[result.size()]); 18 } 19 public void backtracking(char[] chars, boolean[] used){ 20 //如果暂存的path长度等于字符数组的长度,说明已经找到一个 21 if (temp.length() == chars.length) { 22 result.add(temp.toString()); 23 return; 24 } 25 for (int i = 0; i < chars.length; i++){ 26 if (i > 0 && chars[i] == chars[i-1] && used[i-1] == false){ 27 continue; 28 } 29 if (used[i] == false){ 30 used[i] = true; 31 temp.append(chars[i]); 32 //在排列剩下的 33 backtracking(chars, used); 34 //回溯,弹出当前这一个,回到上一步的位置 35 temp.deleteCharAt(temp.length() - 1); 36 //将used回到初始状态 37 used[i] = false; 38 } 39 } 40 } 41 }
小感悟:
第一次遇到回溯,有点难度,还需要多看看才能彻底自己做出来~
标签:offer38,字符,used,Java,temp,chars,数组,回溯,字符串 From: https://www.cnblogs.com/liu-myu/p/17302473.html