JZ38 字符串的排列

描述

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


 


 


 


 


 


 


 ，求其中所有字符的全排列 字符串中可能有重复字符 
 
 
 
 
 
 
 
，打印顺序任意 字符串中只包含大小写字母

思路

都是求元素的全排列
   
   
   
   
   
   
   
 ，字符串与数组没有区别
 

 

 

 

 

 

 

 ，一个是数字全排列 

 

 

 

 

 

 

 
，一个是字符全排列
 


 


 


 


 


 


 


 。为了便于去掉重复情况               ，还是参照数组全排列

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，优先考虑字典序排序














，因为排序后重复的字符就会相邻                       ，后序递归找起来也很方便 使用临时变量去组装一个全排列情况：每当我们选取一个字符以后
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，就确定了其位置






















，相当于对字符串中剩下的元素进行全排列添加在该元素的后面               ，给剩余部分进行全排列就是一个子问题
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，因此可以使用递归 
 
 
 
 
 
 
 
。 终止条件：临时字符串中选取了n个元素














，已经形成了一种排列情况 
  
  
  
  
  
  
  
，可以将其加入输出数组中
   
   
   
   
   
   
   
 。 返回值：每一层给上一层返回的就是本层级在临时字符串中添加的元素
  
  
  
  
  
  
  
 ，递归到末尾的时候
 


 


 


 


 


 


 


 ，就能添加全部元素 具体做法 先对字符串按照字典序排序 
 
 
 
 
 
 
 
，获得第一个排列情况 准备一个空串
   
   
   
   
   
   
   
 ，暂存递归过程中组装的排列情况
 

 

 

 

 

 

 

 。使用额外的vis数组用于记录哪些位置的字符被加入了 每次递归从头遍历字符串
 

 

 

 

 

 

 

 ，获取字符加入：首先根据vis数组 

 

 

 

 

 

 

 
，已经加入的元素不能再加入了；同时               ，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，且str[i-1]已经用














，也不需要将其加入 进入下一等递归前将vis数组当前位置标记为使用过 回溯时                       ，需要修改vis数组当前位置标记
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，同时去掉刚刚加入的字符串元素 临时字符串长度达到原串长度就是一种排列情况

代码

package mid.JZ38字符串的排列; import java.util.ArrayList; import java.util.Arrays; public class Solution { private StringBuilder builder = new StringBuilder(); private ArrayList<String> res = new ArrayList<>(); public ArrayList<String> Permutation(String str) { if (str == null || str.length() == 0) { return res; } char[] chars = str.toCharArray(); Arrays.sort(chars); String sortedStr = new String(chars); //当vis[i]=0






















，表示index为0的字符没有被使用 //当vis[i]=1               ，表示index为1的字符被使用了 int[] vis = new int[chars.length]; dfs(sortedStr, vis, 0); return res; } private void dfs(String str, int[] vis, int depth) { if (builder.length() == str.length()) { res.add(builder.toString()); return; } for (int i = 0; i < str.length(); i++) { if (vis[i] == 1) { continue; } //当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了 if (i != 0 && str.charAt(i) == str.charAt(i - 1) && vis[i - 1] == 1) { continue; } builder.append(str.charAt(i)); vis[i] = 1; dfs(str, vis, depth + 1); builder.deleteCharAt(builder.length() - 1); vis[i] = 0; } } public static void main(String[] args) { System.out.println(new Solution().Permutation("ab")); } }