字符串的排列

知识点 字符串 递归

一、描述

        输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

        例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

 数据范围：n < 10n<10
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)

输入描述：

输入一个字符串,长度不超过10,字符只包括大小写字母。

 这道算法题理解起来好难，我是花了好几天，通过看视频教学和相关文章慢慢理解了解题思路。

二、解题思路分析

        首先，我试了好多牛客网上的java版本的答案，都超时了，没找到一个java版本可以运行通过的。虽然都超时了，但是解题思路是可以好好学习的。

        这道题目其实就是数学里的排列组合求字符串共有多少种不同的组合方式。我们完全可以按照数学解题思路来分析这道题。

        字符串包含n个字符，求其排列组合。 

1、先确定第一个位置有多少种可能性，从n个字符中选择1个字符放在第一个位置，共有n种选择；

2、在第一个位置的字符已经确定的情况下，再从剩下的（n-1）个字符中选择一个字符放在第二个位置上， 共有（n-1）种选择；

3、同理、第3、4、...n的位置。

4、最后算出不关系是否重复的话，共有n*(n-1)*(n-2)*...*2*1 = n!

细品可以发现，里面有递归的意思。其实，网上的解法也是按照这个思路来设计的算法的。

总之一句话概括：

        从前往后依次确定字符数组中每一个位置上的摆放字符的可能性，当最后一个位置上的字符也确定时，就是所有可能的字符串排列。

三、代码设计

import java.util.ArrayList;
import java.util.Comparator;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> results = new ArrayList<>();
        if (str != null && str.length() > 0) {
            char[] chars = str.toCharArray();
            process(chars, results, 0);
        }
        results.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        return results;
    }

    private void process(char[] chars, ArrayList<String> results, int index) {
        if (index == chars.length - 1) {
            if (!results.contains(new String(chars))) {
                results.add(new String(chars));
                return;
            }
        } else {
            for (int j = index; j < chars.length; j++) {
                swap(chars, index, j);
                process(chars, results, index + 1);
                swap(chars, index, j);
            }
        }
    }

    // 交换
    private void swap(char[] str, int i, int j) {
        if (i != j) {
            char t = str[i];
            str[i] = str[j];
            str[j] = t;
        }
    }
}

代码分析：

        results是存放字符串的数组列表，来存放字符串所有的排列组合；

        函数参数index参数，表示要确定字符数组中第index位置上摆放的字符，所以index得初始值为0；

        process()函数中，先来看for循环把，循环遍历j从index开始遍历，因为index之前的位置都已经确定好摆放的字符了。当index=0时，循环中的逻辑是把字符数组中所有位置的字符都和0进行调换，这样字符数组的0位置处就包含了所有情况了。0位置字符确定后，接下来确定1位置的字符，所以index + 1传入process()中去确认第二个位置的字符，依次递归遍历到字符数组第n个位置的字符。

        “index == chars.length - 1"说明前n-1个位置上的元素都确定好字符了，要确定第n个位置上的字符，因为最后一个位置上的字符就只有一种可能性了，所以这时候就是递归的结束条件。判断此时的字符数组代表的字符串是否在列表中，如果不在，则加入到列表中。

        倒数第二个位置上有两种可能性，所以要确认倒数第二个位置上的第二种可能字符的时候，需要先复原一些倒数第二个字符，即还原现场。

其实上面可能还不太好理解，那么来从大的方向考虑;

        第0个位置上要取遍所有的可能性，所以循环中首先就把字符数组的0和0（包括0）之后的所有字符都交换了一下，这样就保证了0位置覆盖所有情况；

        接着要确定第1、2、3...n位置上的字符。这里用的递归。并且递归到index之前的字符都已经确定了，所以index位置的取值范围只能是index及其之后的字符了。着也就是为什么for循环中是这样写的：for (int j = index; j < chars.length; j++)

        在for循环中的下一次循环前，还需要复原一下字符数组，这样能确保位置index之后的所有字符是和位置index上的字符进行交换。这点很重要。