LeetCode 面试题 08.08. 有重复字符串的排列组合 【回溯算法】【哈希】【剪枝】

题目

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

输入：S = “qqe”

输出：[“eqq”,“qeq”,“qqe”]

示例2:

输入：S = “ab”

输出：[“ab”, “ba”]

提示:

字符都是英文字母。

字符串长度在[1, 9]之间。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutation-ii-lcci

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

回溯算法

解法一：哈希表去重

class Solution {
    public String[] permutation(String S) {
        Set<String> res = new HashSet<>();
        char[] arr = S.toCharArray();
        boolean[] vis = new boolean[arr.length];
        backtracing(arr,res,"",vis);
        String[] r = new String[res.size()];
        int i=0;
        for(String s:res){
            r[i++] = s;
        }
        return r;
    }
    public void backtracing(char[] arr,Set<String> res,String s,boolean[] vis){
        if(s.length()==arr.length){
            res.add(s);
            return;
        }
        for(int i=0;i<arr.length;i++){
            if(!vis[i]){
                vis[i]=true;
                backtracing(arr,res,s+arr[i],vis);
                vis[i]=false;
            }
        }
    }
}
           

解法二：排序剪枝去重

class Solution {
    public String[] permutation(String S) {
        List<String> res = new ArrayList<>();
        char[] arr = S.toCharArray();
        Arrays.sort(arr);
        boolean[] vis = new boolean[arr.length];
        backtracing(arr,res,"",vis);
        String[] r = new String[res.size()];
        for(int i=0;i<r.length;i++){
            r[i] = res.get(i);
        }
        return r;
    }
    public void backtracing(char[] arr,List<String> res,String s,boolean[] vis){
        if(s.length()==arr.length){
            res.add(s);
            return;
        }
        for(int i=0;i<arr.length;i++){
            if(vis[i]||(i>0&&(arr[i]==arr[i-1])&&vis[i-1])) continue;
            vis[i]=true;
            backtracing(arr,res,s+arr[i],vis);
            vis[i]=false;
        }
    }
}