题解 | #字符串的排列#

和《有重复数字的全排列》是一样的，有两种解法，第一种是使用选择和撤销，第二种是交换

解法1: 选择和撤销

每个位置的值都可以从所有的元素中选择，选择了当前位置的元素之后，再选下一个元素的，知道选完所有的值，得到一条结果

然后撤销，让当前位置选下一个元素，如此循环，知道该位置选了不同的元素

import java.util.*;



public class Solution {
    ArrayList<String> result = new ArrayList<String>();

    public ArrayList<String> Permutation(String str) {
        String[] input = str.split("");
        LinkedList<String> item = new LinkedList<String>();
        boolean[] visited = new boolean[input.length];
        Arrays.sort(input);
        // 全排列可能会有重复
        // 选择撤销 加一个数组visited
        permutate(input, item, visited);
        return result;
    }

    private void permutate(String[] input, LinkedList<String> item,
                           boolean[] visited) {
        if (item.size() == input.length) {
            result.add(String.join("", item));
            return;
        }

        for (int index = 0; index < input.length; index++) {
            // 不可以选的是，同一级里面，上一个一样的已经选择了，这个就不能再选了
            if (visited[index] || index > 0 && visited[index - 1] == true &&
                    input[index - 1].equals(input[index]) ) {
                continue;
            }

            item.add(input[index]);
            visited[index] = true;
            permutate(input, item, visited);
            item.removeLast();
            visited[index] = false;
        }
    }

}

解法2:交换

每个位置都可以跟它后面的元素进行交换，其实也就是决定当前这个位置start是什么值

选中了start跟某个元素交换后

再对后面的元素也做交换，直到所有的位置都交换结束（终止条件）

然后再让它还原，start的位置再选择下一个元素

import java.util.*;
public class Solution {
    Set<String> result = new HashSet<String>();

    public ArrayList<String> Permutation(String str) {
        String[] input = str.split("");
        permutate(0, input);
        return new ArrayList<String>(result);
    }

    private void permutate(int start, String[] input) {
        if (start == input.length - 1) {
            result.add(String.join("", input));
            return;
        }

        for (int index = start; index < input.length; index++) {
            swap(input, start, index);
            permutate(start + 1, input);
            swap(input, start, index);
        }
    }

    private void swap(String[] input, int a, int b) {
        String temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }
}