题目

描述

输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串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;
  }
}

时间复杂度： $O(n*n!)$ ,全排列总数为n!,JDK中的substring时间复杂度为 $O(n)$ ；
空间复杂度： $O(n!)$ ，存储排列总数。
方法二

思路
找出一个字符串的全排列，就相当于数学问题中的给定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);
  }
}

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

题解 | #字符串的排列#

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤