题目地址：字符串的排列_牛客题霸_牛客网

题目回顾：

解题思路：

这里用到了全排列和剪枝。

首先我们来说全排列，设置一个vis数组来记录当期元素是否被使用过，然后dfs遍历整个数组，列出所有符合条件的路径就是全排列。那么如果数组中有相同元素，将其作为路径开头是不是就会出现路径重复的问题呐？

这里就要用到剪枝操作了，将整个数组排序后，相同元素必然相邻，在同一层的相同元素要进行剪枝操作，当vis[i-1]=false，相邻且arr[i-1]没有被访问过时，就表示当前是同一层。进行剪枝操作。在本题中直接跳过arr[i]作为dfs开头的路径就ok。

整体代码：

    public ArrayList<String> Permutation (String str) {ArrayList<String> res = new ArrayList<>();if (str == null || str.length() == 0)return res;char[] chars = str.toCharArray();Arrays.sort(chars);boolean[] vis = new boolean[str.length()];Arrays.fill(vis,false);StringBuilder temp = new StringBuilder();recursoin(res,chars,temp,vis);return res;}private void recursoin(ArrayList<String> res, char[] chars, StringBuilder temp, boolean[] vis) {if (temp.length() == chars.length){res.add(new String(temp));return;}for (int i = 0; i < chars.length; i++) {if (vis[i])continue;if (i>0 && chars[i-1] == chars[i] && !vis[i-1])continue;vis[i] = true;temp.append(chars[i]);recursoin(res,chars,temp,vis);vis[i] = false;temp.deleteCharAt(temp.length() - 1);}}