剑指Offer - [38] 字符串的排列

2020/06/22

问题描述

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

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

补充:字符串中可能存在重复字符。

举个例子:

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

类似题:

[47] Permutations II

Update at 2020_0907

调整变量名,合并跳过条件:

class Solution {

    List<String> ans = new LinkedList<>();

    private void dfs(char[] ch, StringBuilder sb, int u, boolean[] used){

        if (sb.length() == ch.length){
            ans.add(new String(sb));
            return;
        }

        for (int i = 0; i < ch.length; i++){
            if (used[i] || i > 0 && ch[i] == ch[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            sb.append(ch[i]);
            dfs(ch, sb, u + 1, used);
            sb.setLength(sb.length() - 1);
            used[i] = false;
        }
    }

    public String[] permutation(String s) {
        int n = s.length();
        var used = new boolean[n];
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        dfs(ch, new StringBuilder(), 0, used);
        return ans.toArray(new String[0]);
    }
}

解法1

有三点需要注意下:

第一,需要原始字符串转化成字符数组,便于排序。

char[] arr = s.toCharArray();
Arrays.sort(arr);

第二,使用used布尔数组防止重复的排列。

for (int i = 0; i < arr.length; i++){
    if (used[i]) continue;
    if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) continue;
    ...
    used[i] = true;
    ...
    used[i] = false;
    ...
}

第三,将List<String>转换成String[]

return ans.toArray(new String[0]);

来看下实现:

class Solution {
    public String[] permutation(String s) {
        
        List<String> ans = new LinkedList<>();
        if (s.length() == 0) return new String[0];
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        bt(arr, ans, new StringBuilder(), new boolean[s.length()]);
        // Convert List<String> to String[]
        return ans.toArray(new String[0]);
    }

    private void bt(char[] arr, List<String> ans, StringBuilder sb, boolean[] used){

        // condition
        if (sb.length() == arr.length){
            ans.add(new String(sb));
            return;
        }

        for (int i = 0; i < arr.length; i++){
            if (used[i]) continue;
            if (i > 0 && arr[i] == arr[i - 1] && !used[i - 1]) continue;
            sb.append(arr[i]);
            used[i] = true;
            bt(arr, ans, sb, used);
            used[i] = false;
            sb.setLength(sb.length() - 1);
        }
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory