题解 | 字符串的排列

import java.util.*;


public class Solution {
    // 递归与回溯
    // 如果是线性递归，子问题直接回到父问题不需要回溯，但是如果是树状递归，父问题有很多分治，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支
    public void recursion(ArrayList<String> res, char[] str, StringBuilder temp, boolean[] vis){
        //临时字符串满了加入输出
        if(temp.length() == str.length){
            res.add(temp.toString());
            return;
        }
        // 遍历所有元素选取一个加入
        for(int i = 0;i<str.length;i++){
            // 如果该元素已经被加入了则不需要再加入了
            if(vis[i]){
                continue;
            }
            if(i > 0 && str[i - 1] == str[i] && !vis[i - 1]){
                //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
                continue;
            }
            // 标记为使用过
            vis[i] = true;
            // 加入临时字符串
            temp.append(str[i]);
            recursion(res,str,temp,vis);
            // 回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> res = new ArrayList<String>();
        if(str == null || str.length() == 0){
            return res;
        }
        // 转字符数组
        char[] charStr = str.toCharArray();
        // 按字典序排序
        Arrays.sort(charStr);
        boolean[] vis = new boolean[str.length()];
        // 标记每个位置的字符是否被使用过
        Arrays.fill(vis,false);
        StringBuilder temp = new StringBuilder();
        // 递归获取
        recursion(res, charStr, temp, vis);
        return res;

    }
}