38.字符串的排列

raylan.chen大约 4 分钟

之前学过 Carl 哥的回溯三部曲 - 代码随想录，趁着还有点印象，自己磕磕碰碰地尝试着做了下

class Solution {
    List<Character> path = new ArrayList<>();
    List<Character> tmpGoods = new ArrayList<>();
    List<String> res = new ArrayList<>();

    public String[] goodsOrder(String goods) {
        if (goods == null) return null;

        //tmpGoods 临时存储 变化的 goods
        //每一层可选的 goods 元素是变化的，根据 上一层元素 选择的不同，下一层 goods 可选择的元素也不同
        for (int i = 0; i < goods.length(); i++) {
            tmpGoods.add(goods.charAt(i));
        }

        recursion();

        return res.toArray(new String[0]);
    }

    public void recursion() {
        //递归终止
        if (tmpGoods.size() == 0) {
            res.add(path.stream().map(String::valueOf).collect(Collectors.joining()));
            return;
        }
        Set<Character> set = new HashSet<>();
        
        for (int i = 0; i < tmpGoods.size(); i++) {
            if (!set.contains(tmpGoods.get(i))) {
                //防止同一层的重复
                set.add(tmpGoods.get(i));
                path.add(tmpGoods.get(i));
                char c = tmpGoods.remove(i);
                //下一层
                recursion();
                //回溯
                path.removeLast();
                tmpGoods.add(i, c);
            }
            
        }
    }
}

虽然磕磕碰碰的做出来了，但应该还有很多优化空间

思路：

回溯，（可以把回溯搜索的遍历过程抽象成树形结构，参考：代码随想录，层代表树的层数）
遍历每一层不同的元素，选中某一层的某一个元素后，递归调用，进入下一层元素的选择，遍历完子集合后，需要更换同一层的不同元素，继续遍历子集合
用 List 存放每一层变化的 goods 元素
用另外一个 List 存放每一个符合条件的结果
再用一个 List 存放结果集
注意使用 Set 来防止同一层重复元素的遍历

优秀题解

注意 Carl 哥的返回结果需要改下

class Solution {
    //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树支重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }
}

作者：代码随想录
链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solutions/839108/dai-ma-sui-xiang-lu-jian-zhi-offer-38-zi-gwt6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    List<String> res = new LinkedList<>();
    char[] arr;
    public String[] goodsOrder(String goods) {
        arr = goods.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == arr.length - 1) {
            res.add(String.valueOf(arr));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < arr.length; i++) {
            if(set.contains(arr[i])) continue; // 重复，因此剪枝
            set.add(arr[i]);
            swap(i, x);                      // 交换，将 arr[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solutions/178988/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

38.字符串的排列

38.字符串的排列

参考链接

个人尝试

优秀题解