【剑指Offer】字符串的排列

Posted on | In ,

题目

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

实现

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
public ArrayList<String> Permutation(String str) {
    ArrayList<String> result = new ArrayList<>();
    HashSet<String> set = new HashSet<>();

    if (str != null && str.length() != 0) {
        Permutation(str.toCharArray(), 0, set);
        result.addAll(set);
        Collections.sort(result);
    }

    return result;
}

private void Permutation(char[] str, int pos, HashSet<String> result) {
    if (pos == str.length - 1) {
        result.add(String.valueOf(str));
        return;
    }

    for (int i = pos; i < str.length; i++){
        swap(str, i, pos);
        Permutation(str, pos + 1, result);
        swap(str, pos, i);
    }

}

private void swap(char[] str, int i, int j) {
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

相关题目

  1. 输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上，使得正方体上三组相对的面上的4个顶点的和都相等。

  2. 在8x8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。请问总共有多少种符合条件的摆法？