剑指 Offer 38. 字符串的排列

1. 题目

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

2. 示例

输入：s = "abc"

输出：["abc","acb","bac","bca","cab","cba"]

3. Code

3.1 回溯+交换

public class PermutationB {
    public String[] permutation(String s) {
        HashSet<String> ans = new HashSet<>();
        char[] str = s.toCharArray();
        perm(str, 0, s.length() - 1, ans);
        return ans.toArray(new String[ans.size()]);
    }
    public static void perm(char[] str, int start, int end, HashSet<String> ans) {
        /**
         * @Method: perm
         * @Author: haifwu
         * @Version:  1.0
         * @Date: 21/05/2021 15:50
         * @param str
         * @param start
         * @param end
         * @param ans
         * @Return: void
         * @Description: 回溯 +交换
         */
        if(start == end) {
            StringBuffer sb = new StringBuffer();
            for (char s : str) {
                sb.append(s);
            }
            ans.add(sb.toString());                  // 添加排序方案
        } else {
            for(int i = start; i <= end; i++) {
                swap(str, start, i);                  // 交换，将i固定到第x位
                perm(str, start + 1, end, ans); // 开启固定第x+1位字符
                swap(str, start, i);                  // 恢复交换
            }
        }
    }

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

    public static void main(String[] args) {
        String s = "abcd";
        for(String str : new PermutationB().permutation(s)) {
            System.out.println(str);
        }
    }
}