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

青旅半醒 2023-02-21 11:40 52阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

###### 回溯法 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
**时间复杂度：O(N!) 空间复杂度：O(N^2)**  
![在这里插入图片描述][20200630111232217.png]

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);
    
            // 由于操作的都是字符，使用 StringBuilder
            StringBuilder 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\]的语法解释（指定泛型） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

###### 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/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630111151954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200630111232217.png]: https://img-blog.csdnimg.cn/20200630111232217.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200630111547743.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70