欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指offer】字符的全排列

程序员文章站 2024-03-22 14:57:16
...

????题目

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

输入:s = “abc”
输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

 

☘️解析

显然,这是一个「全排列」问题。
全排列的模板(即swap交换法)不再赘述,本题的关键在于「去重」。

去重思路一:所有可能的排列结果(字符串)都存到Set集合中,让容器帮我们完成去重的操作。

去重思路二:每一次swap的本质是固定一次index处的字符,那么如果每种字符只在index处固定一次,就可以保证去重。

 

????代码

全排列模板+去重思路一:

class Solution {
    public String[] permutation(String s) {
        DFS(s.toCharArray(), 0);
        return res.toArray(new String[res.size()]);
    }

    private Set<String> res = new HashSet<>();

    private void DFS(char[] arr, int index) {
        if (index == arr.length) {
            res.add(new String(arr));
            return;
        }
        for (int i = index; i < arr.length; i++) {
            char temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            DFS(arr, index + 1);
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

全排列模板+去重思路二:

class Solution {
    public String[] permutation(String s) {
        DFS(s.toCharArray(), 0);
        return res.toArray(new String[res.size()]);
    }

    private List<String> res = new ArrayList<>();

    private void DFS(char[] arr, int index) {
        if (index == arr.length) {
            res.add(new String(arr));
            return;
        }
        Set<Character> set = new HashSet<>();
        for (int i = index; i < arr.length; i++) {
            if (set.contains(arr[i])) {
                continue;
            }
            set.add(arr[i]);
            char temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
            DFS(arr, index + 1);
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

 

????补充

1)算法课上多次强调,全排列的时间复杂度是 O(n * n!)

2)做一个区分:全排列问题使用的是swap模板,这有别于一般的回溯模板。这是因为全排列问题可以改变元素之间的相对顺序。