定制网站报价,百度网站建设需要钱,如何做电商带货,像饿了码的网站建站有吗【问题描述】[中等]
输入一个字符串#xff0c;打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组#xff0c;但里面不能有重复元素。示例:
输入#xff1a;s abc
输出#xff1a;[abc,acb,bac,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组但里面不能有重复元素。示例:
输入s abc
输出[abc,acb,bac,bca,cab,cba]限制
1 s 的长度 8【解答思路】
回溯法 时间复杂度O(N!) 空间复杂度O(N^2)
class Solution {ListString res new LinkedList();char[] c;public String[] permutation(String s) {c s.toCharArray();dfs(0);return res.toArray(new String[res.size()]);}void dfs(int x) {if(x c.length - 1) {res.add(String.valueOf(c)); // 添加排列方案return;}HashSetCharacter set new HashSet();for(int i x; i c.length; i) {if(set.contains(c[i])) continue; // 重复因此剪枝set.add(c[i]);swap(i, x); // 交换将 c[i] 固定在第 x 位 dfs(x 1); // 开启固定第 x 1 位字符swap(i, x); // 恢复交换}}void swap(int a, int b) {char tmp c[a];c[a] c[b];c[b] tmp;}
}
2.
时间复杂度O(N) 空间复杂度O(1)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Solution {public String[] permutation(String s) {int len s.length();if (len 0) {return new String[0];}// 转换成字符数组是常见的做法char[] charArr s.toCharArray();// 排序是为了去重方便Arrays.sort(charArr);// 由于操作的都是字符使用 StringBuilderStringBuilder path new StringBuilder();boolean[] used new boolean[len];// 为了方便收集结果使用动态数组ListString res new ArrayList();dfs(charArr, len, 0, used, path, res);// 记得转成字符串数组return res.toArray(new String[0]);}/*** param charArr 字符数组* param len 字符数组的长度* param depth 当前递归深度* param used 当前字符是否使用* param path 从根结点到叶子结点的路径* param res 保存结果集的变量*/private void dfs(char[] charArr,int len,int depth,boolean[] used,StringBuilder path,ListString res) {if (depth len) {// path.toString() 恰好生成了新的字符对象res.add(path.toString());return;}for (int i 0; i len; i) {if (!used[i]) {if (i 0 charArr[i] charArr[i - 1] !used[i - 1]) {continue;}used[i] true;path.append(charArr[i]);dfs(charArr, len, depth 1, used, path, res);// 递归完成以后需要撤销选择递归方法执行之前做了什么递归方法执行以后就需要做相应的逆向操作path.deleteCharAt(path.length() - 1);used[i] false;}}}public static void main(String[] args) {Solution solution new Solution();String[] res solution.permutation(aba);System.out.println(Arrays.toString(res));}
}
【总结】
1.回溯法 剪枝恢复状态
2.collection.toArray(new String[0])中new String[0]的语法解释指定泛型 3. 写法二会比写法一 好理解
转载链接https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/ 参考链接https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/hui-su-suan-fa-java-by-liweiwei1419/
