字典打印所有字符的全排列-剑指offer-Java

傷城~ 2021-12-10 12:34 100阅读 0赞

## 题目描述 ##

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

### 解决思路：递归 ###

剑指offer代码：

> 1.  import java.util.ArrayList;
> 2.  import java.util.Collections;
> 3.  public class Solution \{
> 4.      public ArrayList<String> Permutation(String str) \{
> 5.             ArrayList<String> res=new ArrayList<String>();
> 6.          if(str.length()==0||str==null)return res;
> 7.          int n= str.length();
> 8.          helper(res,0,str.toCharArray());
> 9.          Collections.sort(res);
> 10.         return res;
> 11.          
> 12.     \}
> 13.     public void helper( ArrayList<String> res,int index,char \[\]s)
> 14.     \{
> 15.         if(index==s.length-1)res.add(new String(s));
> 16.         for(int i=index;i<s.length;i++)
> 17.         \{
> 18.             if(i==index||s\[index\]!=s\[i\])
> 19.             \{
> 20.                 swap(s,index,i);
> 21.                 helper(res,index+1,s);
> 22.                 swap(s,index,i);
> 23.             \}
> 24.         \}
> 25.          
> 26.     \}
> 27.      
> 28.     public void swap(char\[\]t,int i,int j)
> 29.      \{
> 30.         char c=t\[i\];
> 31.         t\[i\]=t\[j\];
> 32.         t\[j\]=c;
> 33.     \}
> 34. \}

本机测试代码：

> 1.  package pratice713;
> 2.  import java.util.ArrayList;
> 3.  public class combinStringAll713 \{
> 4.      public static void main(String\[\] args) \{
> 5.          String str ="abcd";
> 6.          String str2="abc";
> 7.          String str3="aaaa";
> 8.        ArrayList list = Permutation(str2);
> 9.        for(int i=0;i<list.size();i++)\{
> 10.           System.out.print(list.get(i)+" ");
> 11.       \}
> 12.     \}
> 13.     public static ArrayList<String> Permutation(String str) \{
> 14.            char strc\[\] = str.toCharArray();
> 15.            ArrayList<String> list = new ArrayList<String>();
> 16.            if(strc.length==0 || str==null) return list;
> 17.           change(strc,0,str.length(),list);
> 18.            
> 19.            return list;
> 20.        \}
> 21.        public static void change(char strc\[\],int start,int end,ArrayList<String> list)\{
> 22.            if( start==strc.length-1) \{
> 23.                //if(!list.contains(String.valueOf(strc)))\{
> 24.                    list.add(String.valueOf(strc));
> 25.                 System.out.println(String.valueOf(strc)+" ");
> 26.              //  \}
> 27.            \}else \{
> 28.                for(int i=start;i<strc.length ;i++)\{
> 29.                    if(i!= start && strc\[start\]==strc\[i\])
> 30.                        continue;
> 31.                    swap(strc,start,i);
> 32.                    change(strc,start+1,end,list);
> 33.                    swap(strc,i,start);
> 34.                \}
> 35.            \}
> 36.        \}
> 37.        public static void swap(char strc\[\],int i,int j)
> 38.        \{
> 39.            char temp = strc\[i\];
> 40.            strc\[i\] = strc\[j\];
> 41.            strc\[j\] = temp;
> 42.        \}
> 43. \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211210/3e89647618d84511b1afcfcdb25904dc.png