[剑指offer]面试题第[38]题[JAVA][字符串的排列][回溯法]

【问题描述】[中等]

输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。示例: 输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]限制： 1 <= s 的长度 <= 8

【解答思路】

回溯法

时间复杂度：O(N!) 空间复杂度：O(N^2)

class Solution {List<String> 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;}HashSet<Character> 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];// 为了方便收集结果，使用动态数组List<String> 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,List<String> 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/

总结

以上是生活随笔为你收集整理的[剑指offer]面试题第[38]题[JAVA][字符串的排列][回溯法]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。