JZ38 字符串的排列
JZ38 字符串的排列
描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：n < 10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
输入描述：输入一个字符串，长度不超过10，字符只包括大小写字母。
示例1
输入：
"ab"
返回值：
["ab","ba"]
// 说明：返回["ba","ab"]也是正确的
示例2
输入：
"aab"
返回值：
["aab","aba","baa"]
示例3
输入：
"abc"
返回值：
["abc","acb","bac","bca","cab","cba"]
解析
本题是一个很经典的问题：求全排列。虽然一开始写的时候无从下手，但看了一会书中的解析就有了思路。
其实思路也是比较简单的，以字符串 ABC 为例，拿到一个字符串求它的全排列，可以分为两个步骤：
- 让字符串的每个字符都当一次第一个字符，可以得到 ABC、BAC、CBA，第一个位置的排列就完成了，在程序中可以使用循环实现；
- 排好第一个字符后，将获得的所有字符串的后面部分再次应用第一步，又能获得每个字符串对应的第二个位置的排列，以此类推，在程序中可以使用递归实现。
以上两步就是获得字符串全排列的过程，可以总结为：对字符串每个位置都进行排列，再对排列得到的更多字符串重复应用这一步。这个过程类似一颗树的枝叶越长越多的过程，也就是描述中的递归树（Recursion Tree）。
但是当字符串有重复时，如字符串 ABB，在排列过程中会得到重复的结果，这种结果是我们需要剔除的。我采用的解决方式是使用 Set 集合进行排列好的字符串的唯一存储，在排列完全结束时再将其转化为需要的数组 。
代码清单
import java.util.*;
public class Solution {
public ArrayList Permutation(String str) {
ArrayList result = new ArrayList();
Set strSet = new HashSet();
Swap(str.toCharArray(),0,strSet);
result.addAll(strSet);
return result;
}
public void Swap(char[] chs,int cur,Set strSet){
// 超出范围了，说明递归该结束
if(cur >= chs.length)
return;
// 将当前字符与其后面所有字符都交换一次
// 再后面的交换交给递归
for(int i = cur; i < chs.length; i++){
// 交换得到一个排序
char temp = chs[cur];
chs[cur] = chs[i];
chs[i] = temp;
// 使用 String.valueOf 转换为字符串存入 Set 中
strSet.add(String.valueOf(chs));
// 对此次排序得到的字符串继续排序后面部分
Swap(chs,cur+1,strSet);
// 把本次的交换换回来，以寻找另外的排序
temp = chs[cur];
chs[cur] = chs[i];
chs[i] = temp;
}
}
}
其中用到了较多的辅助类和方法，包括
- 数据结构 Set 集合，保证保存的字符串唯一性；
- String 字符串转换为字符数组的方法
toCharArray()； - 由字符数组获得 String 字符串的方法
String.valueOf(char[] ...)； - 将 Set 集合中的内容放到 ArrayList 数组中，用到
ArrayList.addAll(...)；
总结
其实是比较简单的排列问题，可能思路容易想到但实现的方式比较难想。实现时用到了许多的辅助方法，最终程序的时间复杂度为 O(n!)，对应递归树；空间复杂度 O(n)，对应开辟的 Set 集合的空间。