题目

描述

• 输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
  输入描述：
  输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

方法一

思路

• 暴力枚举，遍历找出所有的排列并去重。

具体步骤

• 代码如下：

  import java.util.*;
  public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res=new ArrayList<>();
        // 字符串为空，返回空
        if(str==null || str.length()==0){
            return res;
        }
        // 转成字符数组
        char[] chars=str.toCharArray();
        ArrayList<String> tmp1=new ArrayList<>();
        ArrayList<String> tmp2=new ArrayList<>();
        // 遍历枚举
        for(int i = 0;i < chars.length;++i){
            if(i == 0){
                tmp1.add(new String(chars[i]+""));
            }else{
                for(int k = 0;k < tmp1.size();++k){
                    String strTmp=tmp1.get(k);
                    String midStr=null;
                    for(int j = 0;j < strTmp.length()+1;++j){
                        // 拼接字符
                        midStr = strTmp.substring(0,j)+
                            chars[i] + strTmp.substring(j);
                        // 去重
                        if(!tmp2.contains(midStr)){
                            tmp2.add(midStr);
                        }
                    }
                }
                tmp1=new ArrayList(tmp2);
                tmp2.clear();
            }
        }
        res=tmp1;
        Collections.sort(res);
        return res;
    }
  }

• 时间复杂度：,全排列总数为n!,JDK中的substring时间复杂度为；
• 空间复杂度：，存储排列总数。

  方法二

  思路

• 找出一个字符串的全排列，就相当于数学问题中的给定n个格子，再给你n个数字，对之进行排列组合，那么在数学中最常用的方法就是固定字符，确定每一个位置的可能字符，最后求出全排列的数量。
• 同理，在这里也可以通过固定字符的方式来找出每一中排列的字符串，也就是使用回溯的方法来进行计算了，譬如对于字符串"abc"，其有下列的排列组合：abc,acb,bac,bca,cab,cba。
• 可以看见当我们固定一个字符时，需要求的就是剩下字符的全排列，也就相当于是一个子问题，所以便存在如下递推公式：
  
  str-str(i),表示去掉第i个字符，当然这个递推公式还需要去重。

具体步骤

• 从第一个字符开始，循环固定每一个字符作为第一个字符；
• 实现递推公式，计算子字符串的排列;
• ArrayList添加字符串需要手动去重。
• 默认系统所给字符串就是升序排列的，实际上测试用例也确实是升序排列的。
• 参考如下示例：
  
• 代码如下

  import java.util.ArrayList;
  public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        // 空，返回空
        if (str == null || str.length() == 0){
            return res;
        }
        // 长度为1，返回该字符串
        if (str.length() == 1){
            res.add(str);
            return res;
        }
        // 递归排列
        subPerm(0,str,res);
        return res;
    }
    private void subPerm(int position,String str,ArrayList<String> res){
        // 所有字符均已排列
        if (position + 1 == str.length()){
            add(res,str);
            return;
        }
        // position之前的字符已经排列过了，对position及之后的字符进行排列
        for (int i = position; i < str.length();++i){
            str = swap(str,position,i);
            subPerm(position + 1,str,res);
        }
    }
    // 交换
    private String swap(String str,int i,int j){
        char temp = str.charAt(i);
        char[] cs = str.toCharArray();
        cs[i] = cs[j];
        cs[j] = temp;
        return new String(cs);
    }
    // 去重
    private void add(ArrayList<String> res,String str){
        if (res.contains(str)){
            return;
        }
        res.add(str);
    }
  }

• 时间复杂度：,递归为全排列总数为n!；
• 空间复杂度：,总共会有n!中排列方式。