打印不重复的字符串全排列(递归)

什么是不重复的字符串全排列，如果是普通字符串全排列，那么

输入：

acc

输出：

acc
acc
cac
cca
cca
cac

要求写出的去重的，也就是会输出：

acc
cac
cca

上代码进行比较吧，后面给出练习例题。

import java.io.BufferedInputStream;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class test {

    public static void arrange1(char[] str, int i) {
        if (i == str.length) {
            System.out.println(str);
        } else {
            for (int j = i; j < str.length; ++j) {
                swap(str, i, j);
                arrange1(str, i + 1);
                swap(str, i, j);
            }
        }
    }

    public static void arrange2(char[] str, int i) {
        if (i == str.length) {
            System.out.println(str);
        } else {
            Set<Character> set = new HashSet<Character>(); // 每一层对应一个set
            for (int j = i ; j < str.length; ++j) {
                if (!set.contains(str[j])) { // 最上面一层的串是起始串，根据起始串思考
                    set.add(str[j]);
                    swap(str, i, j);
                    arrange2(str, i + 1);
                    swap(str, i, j);
                }
            }
        }
    }

    public static void swap(char[] str, int i, int j) {
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        String str = cin.next();
        arrange1(str.toCharArray(), 0);
        System.out.println("======================");
        arrange2(str.toCharArray(), 0);
        cin.close();
    }
}

相关题目： 

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

输入描述:

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

题目链接：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

测试用例会有空串""，此时不添加进集合，还会有"aa"

分析思路（盗图一张）：

AC代码：

import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collections;
import java.util.Comparator;
 
public class Solution {
    ArrayList<String> list = new ArrayList<String>();
    public ArrayList<String> Permutation(String str) {
        if (str.length() != 0) {
            Arrange(str.toCharArray(), 0);
            // 升序可以不用第二个参数，这里cab测试用例在cba前面，说明得排序，我个人觉得是题目有问题，排序偏离了出题人的意图
            Collections.sort(list, new Comparator<String>(){
                public int compare(String s1, String s2) {
                    return s1.compareTo(s2);
                }
            });
        }
        return list;
    }
    private void Arrange(char[] arr, int i) {
        if (i == arr.length) {
            list.add(new String(arr));
        } else {
            Set<Character> set = new HashSet<Character>();
            for (int j = i; j < arr.length; ++j) {
                if (!set.contains(arr[j])) {
                    set.add(arr[j]);
                    if (i != j) {
                        swap(arr, i, j);
                    }
                    Arrange(arr, i + 1);
                    if (i != j) {
                        swap(arr, i, j);
                    }
                }
            }
        }
    }
    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

======================Talk is cheap, show me the code=========================