剑指Offer 28 *字符串的排列

题目描述

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

思路

参考
1.第一种是递归的想法；全排列就是从第一个数字起每个数分别与它后面的数字交换。听起来很难懂，反正我一看就懂了，但是还是不知道递归内部是怎么做的；
我们先看一下核心代码

static  public  void  Permutation(char[] str,int start)             //全排列函数
   {
       if (start==str.length-1) {
           if (hashSet.add(String.valueOf(str))) {
               arrayList.add(String.valueOf(str));
           }
       }
       else
           for (int j = start ; j<str.length;++j)
           {
                   swap(str, start, j);           // 当前这个位置进行交换
                   Permutation(str, start + 1);   //然后紧接着是下一个位置
                   swap(str, start, j);           //还原当前位置
           }
   }

你看懂了没？反正我是没看懂，逐步调试都没弄明白；
我们先不管别的；假设现在有这么一个字符串（a,b,c,d,e）;我们自己手写全排列怎么写呢？首先锁定第一位是a，然后锁定第二位，然后是第三位；这个锁定的值每次可以不一样的呀，那么这些值是哪里的呢？字符串的嘛；交换过来就可以用了嘛；
结合函数观察一下；Permutation()每次都在进行下一位的锁定；j每次+1，是说当前这个位置可以换成是谁；
比如说 (a,b,c,d,e);先去除递归的话，看看下面是在干嘛呢
很显然，就是换第一位嘛，a可以和（b,c,d,e）进行交换；

for (int j = start ; j<str.length;++j)   //此时start=1
           {
                   swap(str, start, j);           // 当前这个位置进行交换
                   swap(str, start, j);           //还原当前位置
           }

然后我们看一下递归是在干嘛:

1	Permutation(str, start + 1);

进行下一位的锁定，也就是说递归的时候，当前start这个位置的元素已经锁定了；然后对于下一位来说，又可以锁定为不同的值；这就是递归的奥秘；

换个想法

或者换一下，我们忽略什么换不换位置的；
（a,b,c,d,e）,对第一位来说我们把它看成两个部分锁定队列（），未锁定队列（a,b,c,d,e）;
然后我们就循环呗，看看谁可以锁定于是就可以变成（a）,（b,c,d,e）;
锁定队列的第一位是a,那自然也可以是b,c,d,e;但是起码有一个已经锁定了；那就把锁定队列补完呗；于是我们寻找下一位；
锁定队列就可以是（a,b）,（a,c）,（a,d），（a，e）;
对每一个情况又有下一步；所以换完一次，进行一次递归，这次递归一直到底，就会得到一个字符串；然后在递归结束，返回上层；先把交换恢复过来，然后进行循环，看一下还有谁可以锁定在这个位置

另外，因为会存在重复情况，可以通过hashset或者从第一个数字起每个数分别与它后面非重复出现的数字交换这两个思路解决

代码

public class Eight {
    public  static  void  main(String [] arg)
    {
            String a= "bbaa";
            Permutation(a);
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.println(arrayList.get(i));
        }
    }
  static   public ArrayList<String> Permutation(String str) {           //用于进行用例判定，调用函数，以及返回结果
        if (str==null||str.length()==0)
            return  null;
        Permutation(str.toCharArray(),0);
      Collections.sort(arrayList);
        return arrayList;
    }
   static ArrayList <String>arrayList = new ArrayList<>();
    static HashSet<String> hashSet  = new HashSet<>();
    static  public  void  Permutation(char[] str,int start)             //全排列函数
    {
        if (start==str.length-1) {
            if (hashSet.add(String.valueOf(str))) {
                arrayList.add(String.valueOf(str));
            }
        }
        else
            for (int j = start ; j<str.length;++j)
            {
                //if (iscanswap(str,start,j)){                  //可以通过判定j是否在前面出现过
                    swap(str, start, j);
                    Permutation(str, start + 1);
                    swap(str, start, j);
            }
    }
   static public  void  swap(char [] str,int i ,int j)
    {
        char temp = str[i];
        str[i]=str[j];
        str[j]=temp;
    }
    static public boolean iscanswap(char[] str , int start , int i)
    {
        for (int k = start;k<i;k++)
        {
            if (str[k]==str[i])
                return false;
        }
        return  true;
    }
}

收获

彻底弄明白了全排列的递归算法；
使用了一下hashset

2017-03-27