字符串排列

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。如下图所示：

上图就是分别把第一个字符a和后面的b、c等字符交换的情形。首先固定第一个字符，求后面所有字符的排列。这个时候我们仍把后面的所有字符分为两部分：后面的字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。

这道题和全排列不一样的地方是全排列1是没有重复全排列，全排列2是有重复但是不要全排列。这道题是没有说，默认是全排列1可以做。

代码一   剑指offer从第一个往后递推

public class Test4 {
    public static void main(String[] args) {
        permutation("abca".toCharArray());
    }

    public static void permutation(char[] chars) {
        // 输入较验
        if (chars == null || chars.length < 1) {
            return;
        }
        // 进行排列操作
        permutation(chars, 0);
    }


    public static void permutation(char[] chars, int begin) {
        // 如果是最后一个元素了，就输出排列结果
        if (chars.length - 1 == begin) {
            System.out.print(new String(chars) + " ");
        } else {
            char tmp;
            // 对当前还未处理的字符串进行处理，每个字符都可以作为当前处理位置的元素
            for (int i = begin; i < chars.length; i++) {
                // 下面是交换元素的位置
                tmp = chars[begin];
                chars[begin] = chars[i];
                chars[i] = tmp;

                // 处理下一个位置
                permutation(chars, begin + 1);
            }
        }
    }

代码二 dfs

public class Test5 {
    public static void main(String[] args) {
        List<String> strings  = Permutation("abc");
        for(String str : strings){
            System.out.println(str);
        }
    }
    static ArrayList<String> returnList = new ArrayList<>();
    public static List<String> Permutation(String str) {
        if(str=="" || str.length() ==0){
            return returnList;
        }
        helper(str.toCharArray(),0);
        Collections.sort(returnList);
        return returnList;
    }
    public static void helper(char[] chars, int index) {
        if(index == chars.length-1){
            String val = String.valueOf(chars);
            if (!returnList.contains(val)) {
                //如果最后list没有这个string，因为可能交换后有重复的
                returnList.add(val);
            }
            return;
        }
        for(int i =index;i<chars.length;i++){
            swap(chars, index, i);
            helper(chars,index+1);
            swap(chars, index, i);
        }
    }
    public static void swap(char[] chars,int i, int j) {//交换数组中的两个位置中的值
        char temp =chars[i];
        chars[i] = chars[j];
        chars[j] = temp;

    }
}

代码三 全排列代码

public static void main(String[] args) {
    List<List<Character>> returnlist = permute("abc".toCharArray());
    for(int i =0;i<returnlist.size();i++){
        System.out.println(returnlist.get(i));
    }


}
static List<List<Character>> list = new ArrayList<>();

public static List<List<Character>> permute(char[] nums) {
    if (nums == null || nums.length == 0) {
        return list;
    }
    List<Character> list1 = new ArrayList<>();
    dpf(nums,list1);
    return list;
}
public static void dpf(char[] nums,List<Character> list1){
    if(list1.size() ==nums.length){
        list.add(new ArrayList<>(list1));
    }else {
        for(int i =0;i<nums.length;i++){
            //如果已经在数组里面了
            if(list1.contains(nums[i])){
                continue;
            }
            list1.add(nums[i]);
            dpf(nums,list1);
            list1.remove(list1.size()-1);
        }
    }
}

代码四 大神解读

/**

 * 题目：

 * 字符串的排列 -- newcoder 剑指Offer 27

 *

 * 题目描述：

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

 * 例如输入字符串abc,则打印出由字符a,b,c 所能排列出来的所有字符串

 * abc,acb,bac,bca,cab和cba。

 *

 * 输入描述:

 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

 */

public class Permutation
{
    /**
     * 思路：
     * 
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，
     * 递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * 由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     * 
     */
    public ArrayList<String> permutation(String str) {
        ArrayList<String> ret = new ArrayList<>();
        
        if (str == null || str.isEmpty()) {
            return ret;
        }
        
        char[] arr = str.toCharArray();
        
        permutation(arr, 0, ret);
        
        Collections.sort(ret);
        return ret;
    }
    
    private void permutation(char[] arr, int begin, ArrayList<String> cache) {
        if (begin == arr.length - 1) {
            cache.add(new String(arr));
            return;
        }
        
        int len = arr.length;
        for (int i=begin; i<len; i++) {
            // 与begin不同位置的元素相等，不需要交换
            if (i!=begin && arr[i]==arr[begin]) {
                continue;
            }
            // 交换元素
            swap(arr, begin, i);
            // 处理后续元素
            permutation(arr, begin+1, cache);
            // 数组复原
            swap(arr, begin, i);
            
        }
    }
    
    private void swap(char[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        arr[i] = (char)(arr[i]^arr[j]);
        arr[j] = (char)(arr[i]^arr[j]);
        arr[i] = (char)(arr[i]^arr[j]);
    }