题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
考察重点
全排列问题，在代码上很直觉的就会想到用递归的方式解决，那么就记住如下几个写递归的关键点：
- 可以划分为更小的子问题来求解
- 递归函数的主体要明确主要的业务逻辑，在单独一次递归时要完成什么操作（先整体）；
- 在实现递归函数时，要明确什么时候进入下一次递归（后局部）；
- 递归函数的入口处要判断递归终止的条件，否则递归调用没有地方退出。
题目详解
先来整体看下这个题目，是否具有递归求解的条件：
对于一个长度为n的字符串str如果要求全排列，那么只要固定str[0]的字符，通过求长度n-1的字符串，就能给这题干出来了（可以划分为更小的子问题）
整体上我们需要一个函数
void permutate(String str, int pos)，含义是从字符串的pos位置到结尾的全排列（整体）-
在划分的子问题上，我们可以固定开始位置的字符，然后去求后面的字符串的全排列（局部，何时进入下一次递归）
例如
permutate(str, 0)是求从0开始的全排列，那就先固定0位置的字符，求后面的字符的全排列permutate(str, 1) 如果字符串长度是1的话，那就不用求了，直接就是个全排列（递归终止条件）
现在这个题的思路就清晰了，下面贴下关键代码。
/**
* 对字符串sb，从pos开始的位置，到字符串的末尾的字符做全排列
* @param pos
* @param sb
* @param ret
*/
private static void recur(int pos, StringBuilder sb, Set<String> ret) {
// 递归终止条件，如果已经到字符串末尾了，没啥全排列的了，放入结果集
if (pos + 1 == sb.length()) {
ret.add(sb.toString());
return;
}
for (int i = pos; i < sb.length(); i++) {
// 从pos位置开始，依次交换pos位置和pos位置以后的字符
swap(sb, pos, i);
// 确定pos位置的字符后，再去求pos + 1位置开始后面字符的全排列
recur(pos + 1, sb, ret);
// 别破环下次循环，交换完了换回来
swap(sb, i, pos);
}
}
完整代码
import java.util.*;
public class Solution {
public static ArrayList<String> Permutation(String str) {
Set<String> retSet = new HashSet<String>();
StringBuilder sb = new StringBuilder(str);
recur(0, sb, retSet);
ArrayList<String> result = new ArrayList<String>(retSet);
// 安装字典序对返回结果进行全排列
Collections.sort(result);
return result;
}
/**
* 对字符串sb，从pos开始的位置，到字符串的末尾的字符做全排列
* @param pos 字符的索引值
* @param sb 要递归的字符串
* @param ret 返回的结果
*/
private static void permutate(int pos, StringBuilder sb, Set<String> ret) {
if (pos + 1 == sb.length()) {
ret.add(sb.toString());
return;
}
for (int i = pos; i < sb.length(); i++) {
swap(sb, pos, i);
permutate(pos + 1, sb, ret);
swap(sb, i, pos);
}
}
/**
* 交换x和y位置的字符
* @param sb
* @param x
* @param y
*/
private static void swap(StringBuilder sb, int x, int y) {
char temp = sb.charAt(x);
sb.setCharAt(x, sb.charAt(y));
sb.setCharAt(y, temp);
}
public static void main(String[] args) {
String test = "aab";
System.out.print(Permutation(test));
}
}
