剑指Offer-29-字符串的排列

80 阅读 0 评论 53 点赞

我是靠谱客的博主小巧小丸子，最近开发中收集的这篇文章主要介绍剑指Offer-29-字符串的排列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
注意：字符可能重复！
比如，aab的所有排列为，aab,aba,baa

解析

预备知识

全排列：n个数按照一定顺序组成的排列，成为全排列。意思就是所有元素都参与排列。这些排列为n!。因为第一个位置可以放n个元素，当第一个确定以后，第二个位置可以放n-1个元素，依次类推，当前n-1个位置都确定好元素后，最后一个位置只能放1个，故总排列数为n*(n-1)...*1=n!。

思路一

我们先考虑不重复时的情况，因为这种简单一点，先从简单出发。对于给定的字符串，要输出字典序的所有的排列。我们可以dfs的思路来做，确切的说利用全排列的定义来做。为了保证字典序，不妨先对给定字符串排序，这样得到第一个字符串必为最小的。比如213，所有的排列为：123 132 213 231 312 321。
我们的思路就是从高位开始，每一个位置都从1,2,3分别取值，只要高位优先取当前剩余的元素的最小值，就能保证生成的字符串仅挨与上一次。为了记录每一轮中以取的值，添加一个访问数组，该数组记录哪些元素已被访问，其索引对应排序后的字符串索引。简单过程如下：
1. 第一个位置从1,2,3开始遍历，取1后，第二位置也从1,2,3遍历，但发现1已被取过，又为了保证最小，所以取，第三个位置也从1,2,3遍历，发现1,2都访问过了，取3，这时组成1,2,3
2. 第三个位置已经没有元素可以遍历，故回溯到上一层中，第二个位置取3，第三个位置发现1已被访问，2没被访问，故取3, 这时组成1,3,2.
3. 第二位置已经没有元素可以遍历了，故回溯到第一个位置了，之后的过程类似。

当前处理重复元素也很简单，有重复元素只不过会导致有重复的排列加入嘛，直接set去重即可。

    /**
     * 带重复字符的全排列问题
     * 利用set来去重
     * @param str
     * @return
     */
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if(str == null || str.equals("")) {
            return result;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        Set<String> set = new LinkedHashSet<>();
        boolean[] vis = new boolean[chars.length];
        char[] temp = new char[chars.length];
        permutation(0, temp, chars, set, vis);
        result.addAll(set);
        return result;
    }