剑指offer 字符串的排列

描述

剑指offer JZ38 字符串的排列
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

方法：递归，回溯

思路：通过递归回溯，遍历出所有字符组合，并且去重

public class Solution {
    //用于储存结果
    static ArrayList<String> list = new ArrayList<>();
    //用于标记数字是否已使用
    static boolean[] flags;
    //目标字符串生成的数组，便于遍历
    static char[] strs;
    //用于拼接字符串，生成单个结果
    static StringBuffer sb = new StringBuffer();
    //主方法，对字符串进行处理并且首次调用递归
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) return list;
        flags = new boolean[str.length()];
        strs = str.toCharArray();
        //将字符串排序，便于去掉重复排列
        Arrays.sort(strs);
        Arrays.fill(flags, false);
        tranverse();
        return list;
    }

    //递归方法，用于遍历所有字符串
    void tranverse() {
        //如果拼接的字符串长度等于原始字符串长度，则遍历完成，
        //将结果添加入结果集
        if (sb.length() == strs.length) {
            list.add(sb.toString());
            return;
        }
        //在每一位遍历所有字符
        for (int i = 0; i < strs.length; i++) {
            //字符在前面已被使用，跳过
            if (flags[i]) continue;
            //这条是用于去掉重复结果。当此字符等于前一个字符，并且前一个字符已被使用的情况下，就跳过此字符。当字符串中存在相同字符的时候，相同字符在新字符串中的位置必须逆序出现，才不会触发这个判断条件。如果触发则此新字符串长度不够，不会被加入结果集。所以保证了只有一种顺序
            if (i > 0 && strs[i] == strs[i - 1] && flags[i - 1]) continue;
            sb.append(strs[i]);
            flags[i] = true;
            tranverse();
            //对字符标记进行回溯
            flags[i] = false;
            //对结果进行回溯
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}