字符串的全排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

考察重点

全排列问题，在代码上很直觉的就会想到用递归的方式解决，那么就记住如下几个写递归的关键点：

1. 可以划分为更小的子问题来求解
2. 递归函数的主体要明确主要的业务逻辑，在单独一次递归时要完成什么操作（先整体）；
3. 在实现递归函数时，要明确什么时候进入下一次递归（后局部）；
4. 递归函数的入口处要判断递归终止的条件，否则递归调用没有地方退出。

题目详解

先来整体看下这个题目，是否具有递归求解的条件：

• 对于一个长度为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));
    }

}