剑指Offer_27

发表于

题目

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

输入描述:

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

解题思路

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

正常人的思维是，固定第一个字符，然后依次将后面的字符串与前面的交换，那么排列的个数就是除了第一个字符以外，其他字符的排列个数+1。

也就是固定一个字符串之后，之后再将问题变小，只需求出后面子串的排列个数就可以得出结果，当然第一时间想到的就是递归的算法了。

下面这张图很清楚的给出了递归的过程：

去重

由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。

换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

这样，我们得到在全排列中去掉重复的规则：
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    private ArrayList<String> A = new ArrayList<>();
    private char []chars;
        
    private void PermutationHelper(int index){
        if(index == chars.length-1){
            A.add(new String(chars));
        }
        for(int i = index; i < chars.length; ++i){
        	//if条件句 去重操作
        	//第一次进入循环  i == index 总是成立
            if(i != index && chars[i] == chars[index]){
                continue;
            }
            swap(i, index);
            PermutationHelper(index+1);
            swap(i, index);
        }
    }
    
    private void swap(int i, int j){
        char x = chars[i];
        chars[i] = chars[j];
        chars[j] = x;
    }
        
    public ArrayList<String> Permutation(String str) {
        if(str == null || str.length() == 0){
            return A;
        }
        chars = str.toCharArray();
        PermutationHelper(0);
        Collections.sort(A);
        
        return A;
    }  
}