剑指 Offer 38. 字符串的排列

in with 0 comment

剑指 Offer 38. 字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

都是使用 DFS,剪枝方法不同

  1. 暴力 DFS,剪去相邻相等的字符,最后使用 Set 去重
  2. DFS 在原数组中交换元素位置,使用 Set 判断是否交换过元素以此出重剪枝。回溯横向固定一个位置,从第一个元素开始交换数组中元素。纵向开始递归,固定下一个元素一直到交换完所有元素,回溯时需要将元素位置重置就是将交换的元素再交换回来,退出递归条件为 x == chars.length - 1,纵向固定次数(从 0 开始)等于数组长度即可。

代码

解法一

class Solution {
    public String[] permutation(String s) {
        Set<String> res = new HashSet<>();
        char[] chars = s.toCharArray();
        dfs(chars, "", res, new boolean[chars.length]);
        return res.toArray(new String[res.size()]);
    }

    void dfs(char[] chars, String str, Set<String> res, boolean[] visited) {
        if (str.length() == chars.length) {
            res.add(str);
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (visited[i]) continue;
            if (i > 0 && chars[i] == chars[i - 1] && visited[i - 1]) continue;
            visited[i] = true;
            dfs(chars, str + chars[i], res, visited);
            visited[i] = false;
        }
    }
}

解法二

class Solution {

    List<String> res = new ArrayList<>();
    char[] chars;

    public String[] permutation(String s) {
        chars = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    void dfs(int x) {
        if (x == chars.length - 1) {
            res.add(String.valueOf(chars));
            return;
        }

        Set<Character> set = new HashSet<>();
        for (int i = x; i < chars.length; i++) {
            if (set.contains(chars[i])) continue;
            set.add(chars[i]);
            swap(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }

    void swap(int a, int b) {
        char tmp = chars[a];
        chars[a] = chars[b];
        chars[b] = tmp;
    }
}