🌕🌗 剑指 Offer 38. 字符串的排列

难度: 🌕🌗

问题描述

---

解法

class Solution {
    ArrayList<String> list = new ArrayList<>();
    char[] array;
    int len;
    public String[] permutation(String s) {
        // 思路：
        // 含重复元素的全排列 - 排序去重
        array = s.toCharArray();
        Arrays.sort(array);
        len = array.length;

        // 回溯
        StringBuilder sb = new StringBuilder();
        int[] used = new int[len];
        mySol(0, sb, used);
        int size = list.size();
        String[] res = new String[size];
        for(int i = 0; i < size; i ++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void mySol(int index, StringBuilder sb, int[] used) {
        // 递归终止条件
        if(index == len) {
            list.add(sb.toString());
            return;
        }
        // index < len
        // 当前下标，从已有元素中选择一个插入
        for(int i = 0; i < len; i ++) {
            if(used[i] == 1) {
                // 说明 这条路径 该节点在前面已经被使用
                continue;
            }
            if(i > 0 && array[i] == array[i - 1] && used[i - 1] == 0) {
                // 说明 这条路径 上一个重复的元素没有被选择，那么之前肯定存在一条路径上一个重复元素被选择
                // 情况已经被考虑，因此 跳过
                continue;
            }
            sb.append(array[i]);
            used[i] = 1;
            mySol(index + 1, sb, used);
            used[i] = 0;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

输出