剑指offerNo27. 字符串的排列（Java）

题目描述：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路：

整体分为两步：

• 求出出现在第一个位置上的字符，即把第一个字符与后面所有的字符进行交换。
• 固定第一个字符，并求后面字符的排列。后面的部分我们同样可以看成两部分，....依次递归进行。

代码：

  

   

    

     

    
    

     

      package offer;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import java.util.ArrayList;
     
    
   

    

     

    
    

     

      import java.util.Collections;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public 
      class TestNo27 {
     
    
   

    

     

    
    

     
    
      public static void main(String[] args) {
     
    
   

    

     

    
    

     

              String s = 
      "abc";
     
    
   

    

     

    
    

     

              System.out.println(
      new TestNo27().Permutation(s));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      public ArrayList<String> Permutation(String str) {
     
    
   

    

     

    
    

     

              ArrayList<String>  res = 
      new ArrayList<>();
     
    
   

    

     

    
    

     
        
      if(str == null || str.length() == 
      0){
     
    
   

    

     

    
    

     
            
      return res;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              helper(res,
      0,str.toCharArray()); 
      //从第一个位置开始递归
     
    
   

    

     

    
    

     

              Collections.sort(res);
      //按字典序排序
     
    
   

    

     

    
    

     
        
      return res;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      private void helper(ArrayList<String> list,int idx,char[] arr){
     
    
   

    

     

    
    

     
        
      if(idx == arr.length
      -1){
     
    
   

    

     

    
    

     
            
      //如果idx到了最后一个字符，说明找到了一个排列
     
    
   

    

     

    
    

     

                  String s = String.valueOf(arr);
     
    
   

    

     

    
    

     
            
      if(!
      list.contains(s)){
     
    
   

    

     

    
    

     
                
      list.add(s); 
      //如果这个排列不在答案列表中
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
      else{
     
    
   

    

     

    
    

     
            
      for(
      int i = idx;i<arr.length;i++){
      //将第i个位置字符和后续所有字符进行交换
     
    
   

    

     

    
    

     

                      swap(arr,idx,i);
      //交换第idx个位置和第i个位置的字符
     
    
   

    

     

    
    

     

                      helper(
      list,idx+
      1,arr);
      //固定了第idx个位置，递归的寻找子序列的全排列
     
    
   

    

     

    
    

     

                      swap(arr,idx,i);
      //交换回来 以便将第idx个位置字符和后续另一个字符进行交换
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      private void swap(char[] arr,int i,int j){
     
    
   

    

     

    
    

     
        
      char temp = arr[i];
     
    
   

    

     

    
    

     

              arr[i] = arr[j];
     
    
   

    

     

    
    

     

              arr[j] = temp;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }