华为面试题--字符串重排

字符串重排：给定一个只包含大写英文字母的字符串S，要求你给出对S重新排列的所有不相同的排列数。 如：S为ABA，则不同的排列有ABA、AAB、BAA三种。

示例 1： 输入: "ABA" 输出: 3 示例 2： 输入: "AABBCC" 输出: 90

解题思路： 先把每个字符当成唯一出现过一次，计算所有排列数；再统计重复出现的字母，除去每个字母的排列次数

public class test1{
    public static void main(String[] args) {
        String s = "AABBCC";
        int n = s.length();
        int allSort = Asort(n);
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        for (char key : map.keySet()) {
            allSort /= Asort(map.get(key));
        }
        System.out.println(allSort);
    }
    public static int Asort(int n){
        if(n == 1)
            return 1;
        return n * Asort(n-1);
    }
}

题目扩展：生成字符串的所有排列（剑指offer38题）

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

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

题解：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/

public class test1{
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[0]);
    }
    public void dfs(int x){
        if(x == c.length - 1){
            res.add(String.valueOf(c));
            return;
        }

        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if (set.contains(c[i]))
                continue;
            set.add(c[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);
        }
    }
    public void swap(int a, int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }

}