记一次leetcode解题：剑指Offer38.字符串的排列

题目详情

  剑指 Offer 38. 字符串的排列

  输入一个字符串，打印出该字符串中字符的所有排列。

  你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

  示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

  限制：

1 <= s 的长度 <= 8

我的解题思路

  我的目标是在能过的基础上，尽可能好。

  初看这道题，虽然是中等难度，但我觉得还是不是特别难。细看这道题，我想起大学老师用Python讲算法时讲的子集的题。当时用了二进制的思想，但不能用在这道题里。

  在开始想过用for来交换进行排列，但太难了。

  后来，我突然想到了用整体和局部视角来看，可将排列分成两个部分，对这两个部分进行排列。

  再后来，我认为，每一个排列都是将一个元素放在上一个排列的左边和右边。如：元素c，上一个排列ab，那么将有排列cab和abc。

  那么根据思路写出如下代码。

class Solution {
    HashSet<String> set = new HashSet<String>();//结果集，进行去重
    
    public String[] permutation(String s) {
        slove(new StringBuffer(""), new StringBuffer(s));//执行
        return set.toArray(new String[set.size()]);
    }
    public void slove(StringBuffer e,StringBuffer s){//e是被排列部分，s中取出的元素看作和空进行排列
        if(s.length() == 1){//只剩一个元素进行排列了进行终止
            String t1 = new String((new StringBuffer(e)).insert(0,s));
            set.add(t1);
            return;
        }
        char t;//要排列的元素，从s中取出
        StringBuffer ss;//对象引用，必须复制一份用于接下来的排列
        for(int i = 0 ;i<s.length();i++){//依次遍历s中的每一个元素进行排列
            t = s.charAt(i);
            ss = new StringBuffer(s);        
            ss.deleteCharAt(i);
            slove((new StringBuffer(e)).insert(0,t),ss);
        }
    }
}

  通过对其他题解进行分析，改为如下。

class Solution {
    HashSet<String> set = new HashSet<String>();
    
    public String[] permutation(String s) {
        slove("", new StringBuffer(s));
        return set.toArray(new String[set.size()]);
    }
    public void slove(String e,StringBuffer s){
        if(s.length() == 1){
            String t1 = e+s;
            set.add(t1);
            return;
        }
        char t;
        StringBuffer ss;
        for(int i = 0 ;i<s.length();i++){
            t = s.charAt(i);
            ss = new StringBuffer(s);        
            ss.deleteCharAt(i);
            slove(e+t, ss);
        }
    }
}
//仅少量变化，注释看上一个

  虽然不知不觉写出了回溯的方法，也进行了一定的剪枝，但是当s里有相同元素时，会出现相同排列。根据我对我看了的几个题解，我认为可以对s进行排序，每次排列时找出当前元素的最大相同的子集，将其视为一个。如，baa，在进行b和a的排列时，可以将aa视为一个a。但这样会不会绕路?

我的错误或者失误

  代码当然不是一下就写好的，当中也出现了许多错误。

1. 许久没写代码了，String和StringBuffer以及其他类的方法不是特别熟悉了。

2. list和set的查找时间复杂度没有第一时间反应出来。

3. 当发现超时和内存超限时，仔细分析才发现排列时把左右都排列会出双倍的重复。如abc，当a和""左右排列以及b和""左右排列后时，下一步会出现ab和ba以及ba和ab（先排右在排左），出现重复工作。如下代码9-12和21-22。

class Solution {
  	ArrayList<String> list = new ArrayList<String>();
    public String[] permutation(String s) { 
        slove(new StringBuffer(""), new StringBuffer(s));
        return list.toArray(new String[list.size()]);
    }
    public void slove(StringBuffer e,StringBuffer s){
        if(s.length() == 1){
            String t1 = new String((new StringBuffer(e)).insert(0,s));
            String t2 = new String((new StringBuffer(e)).append(s));
            if(!list.contains(t1))list.add(t1);
            if(!list.contains(t2))list.add(t2);
            return;
        }
        StringBuffer t;
        StringBuffer ss;
        for(int i = 0 ;i<s.length();i++){
            t = new StringBuffer(""+s.charAt(i));
            ss = new StringBuffer(s);        
            ss.deleteCharAt(i);
            slove((new StringBuffer(e)).insert(0,t),ss);
            slove((new StringBuffer(e)).append(t),ss); 

           
        }
        
    }
   

}