【面试题27-字符串的排列】

剑指offer第二十七题。

题目描述

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

解题思路

这是一个全排列问题，可以用回溯法一一试探。

我的答案

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        //存放结果
        ArrayList<String> res = new ArrayList<>();
       //判断空的情况
        if(str == null){
            return res;
        }
        //下面利用回溯法处理这个字符串的全排列所有情况
        fun(str.toCharArray(),res,0);
        //按照字典排序
        Collections.sort(res);
        //返回结果
        return res;
    }
    
    //回溯获取所有的组合情况
    private void fun(char[] strChar,ArrayList<String> res,int i){
        //主要的思路是：首先固定住i索引处的数字，然后递归对后面的字符递归处理
        
        //如果i已经到了字符数组的最后一位，那么说明这一次已经结束了，添加进结果集即可
        if(i == strChar.length-1){
            //去重
            if(!res.contains(new String(strChar))){
                res.add(new String(strChar));
            }
            return;
        }else{
            //可以举个例子比如就是"abc"
            //①第一波是：swap(arr,0,0)，此时第一个元素还是"a"，即"abc"，下面就是对a后面的元素进行全排列（递归）
                //②第1.1波是：swap(arr,1,1)，此时第一个元素"a"是固定的，第二个元素此时就是"b"，即"abc"
                //③第1.2波是：swap(arr,1,2)，此时第二个元素此时就是"c",即"acb"
            //④第二波是：swap(arr,0,1)，此时第一个元素是"b"，即"bac"，下面就是对b后面的元素进行全排列（递归）
                //⑤第2.1波是：swap(arr,1,1)，此时为"bac"
                //⑥第2.2波是：swap(arr,1,2)，此时为"bca"
            //⑦第三波是：swap(arr,0,2)，此时第一个元素是"c"，即"cba"，下面就是对c后面的元素进行全排列（递归）
                //⑧第3.1波是：swap(arr,2,1)，此时为"cba"
                //⑨第3.2波是：swap(arr,2,2)，此时为"cab"
            //注意，上面的顺序可能与实际不一样
            //停止条件就是i达到了数组的最后一个数字。此时已经对所有的字符组合完毕了，符合条件的就全部装进结果集中
            for(int j=i;j<strChar.length;j++){
                swap(strChar,i,j);
                fun(strChar,res,i+1);
                swap(strChar,i,j);
            }
        }
    }

    //交换数组的两个下标的元素
    private void swap(char[] str, int i, int j) {
        if (i != j) {
            char t = str[i];
            str[i] = str[j];
            str[j] = t;
        }
    }
}