38_字符串的排列.md

字符串的排列

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode） (leetcode-cn.com)

分析

用排列组合的思想，进行回溯递归。

在一个字符串排列中，一个位置的字符只能出现一次，使用一个标记数组来标识当前位置是否使用。题目要求结果中不出现重复字符串，于是需要去重。对于去重：

• 在组合成字符串之后去重，这样会产生格外的重复递归。
• 在递归前判断是否会重复。

1. 组合成字符串之后去重

在递归的判断只有当前位置是否使用，于是使用一个标记数组或者mask来表示当前位置是否使用，即mask & 1 << i，如果等于0表示当前位置未被使用。然后在最后判断组合后的字符串是否重复。

class Solution {
    List<String> res;
    Set<String> seen;

    public String[] permutation(String s) {
        res = new ArrayList<>();
        seen = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        process(s, sb, 0);
        String[] ans = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    private void process(String s, StringBuilder sb, int chosenMask) {
        if (s.length() == sb.length()) {
            String temp = sb.toString();
            if (!seen.contains(temp)) {
                res.add(temp);
                seen.add(temp);
            }
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if ((chosenMask & 1 << i) == 0) {
                sb.append(s.charAt(i));
                process(s, sb, chosenMask | 1 << i);
                sb.delete(sb.length() - 1, sb.length());
            }
        }
    }
}

2. 递归前判断是否重复

使用vis数组来标识当前位置是否使用。那么为了防止相同字符的重复排列，先对字符串的字符进行排序，让相同字符相邻，并且每次排序只使用相同字符中的第一个未被使用的字符。这样可以减少重复递归的次数。

为了使用相同字符中第一个未被使用的字符，可以加入判断：i > 0 && arr[i - 1] == arr[i] && !vis[i - 1]。判断句的含义是：

• 当前位置不是第一个字符。
• arr[i - 1] == arr[i]，当前字符与上个字符相等。
• !vis[i - 1]，上个字符没有被使用。

以上三个条件满足，表示当前字符不是相同字符中第一个未被使用的字符，跳过以这个字符开始的递归。

时间复杂度为O(n×n!)。

class Solution {
    List<String> res;
    boolean[] vis;

    public String[] permutation(String s) {
        int n = s.length();
        res = new ArrayList<>();
        vis = new boolean[n];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        backtrack(arr, sb, n);

        String[] ans = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    private void backtrack(char[] arr, StringBuilder sb, int n) {
        if (sb.length() == n)
            res.add(sb.toString());
        for (int i = 0; i < n; i++) {
            if (vis[i] || i > 0 && arr[i] == arr[i - 1] && !vis[i - 1])
                continue;
            sb.append(arr[i]);
            vis[i] = true;
            backtrack(arr, sb, n);
            sb.deleteCharAt(sb.length() - 1);
            vis[i] = false;
        }
    }

}

3. 得到下一个排列

将字符转化为数字，考虑一种情况。

例如字符串"abc"，转化为数字即为123。使用函数nextPermutation计算由123组成的下一个比其大的数字（132）。从最小的123，每次计算下一个排列，直到最大的321，这就是由123能组成的所有排列组合。

在字符的情况下也是一样。将字符串排序得到最小的字符串，每次通过nextPermutation得到临近的下一个字符串，直到达到最大值，得到的字符串数组就是所有的排列组合。

• 如何计算下一个排列？

以数字来考虑。
对于一个数组arr，要想得到下一个比它大的组合，需要在左侧找到一个[尽可能靠右的]较小数（这样与较大的数交换时才能保证更小的改动幅度），在右侧找到一个[尽可能较小的]较大数。

为了找到尽可能靠右的较小数，选择从末尾反向遍历，找到一个arr[i - 1] < arr[i]即可，那么较小数的坐标had=i-1。

经过遍历可知，had右边的数全是递减序列。那么继续从末尾反向遍历，找到第一个大于arr[had]的数，这个数一定是尽可能小的较大数。

于是交换两者位置，并将had之后的位置重新排序成最小序列即可。

在字符串的转换中，对于初始序列char[] arr，每次得到一个更大的序列并加入res，直到返回的字符串为null即可。

这种直接计算下一个排列的方式，还可以有去重的效果，本身就不会选择重复的字符来组合，还可以减少回溯在递归上的开销。

class Solution {

    public String[] permutation(String s) {
        int n = s.length();
        char[] arr = s.toCharArray();
        Arrays.sort(arr);

        List<String> ret = new ArrayList<>();
        String get = String.copyValueOf(arr);
        while (get != null) {
            ret.add(get);
            get = nextPermutation(arr, n);
        }
        int size = ret.size();
        String[] res = new String[size];
        for (int i = 0; i < size; i++) {
            res[i] = ret.get(i);
        }
        return res;
    }

    private String nextPermutation(char[] arr, int n) {
        int had = -1;
        for (int i = n - 1; i > 0; i--) {
            if (arr[i - 1] < arr[i]) {
                had = i - 1;
                break;
            }
        }
        if (had == -1)
            return null;
        else {
            int last = n - 1;
            while (arr[had] >= arr[last])
                last--;
            char temp = arr[last];
            arr[last] = arr[had];
            arr[had] = temp;
            Arrays.sort(arr, had + 1, n);
            return String.copyValueOf(arr);
        }
    }
}