[NC]121. 字符串的排列

🚩传送门：牛客题目

题目

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc” 输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

解题思路：全排列

我们可以这样思考：当我们已知了当前的一个排列，我们能不能快速得到字典序中下一个更大的排列呢？
当我们已知了当前的一个排列，我们可以在 O(n)O(n) 的时间内计算出字典序下一个中更大的排列。这与 C++ 中的 next_permutation 函数功能相同。

具体地，我们首先对给定的字符串中的字符进行排序，即可得到当前字符串的第一个排列，然后我们不断地计算当前字符串的字典序中下一个更大的排列，直到不存在更大的排列为止即可。

这个方案的优秀之处在于，我们得到的所有排列都不可能重复，这样我们就无需进行去重的操作。同时因为无需使用回溯法，没有栈的开销，算法时间复杂度的常数较小。

复杂度分析

时间复杂度：，其中 为给定字符串的长度。

  - 我们需要 ![](https://cdn.nlark.com/yuque/__latex/ab93e03bac57a0bd07b097cb2dff1f84.svg#card=math&code=%5Csmall%20O%28n%5Ccdot%20log%20n%29&height=23&id=ISG3d) 的时间排序得到第一个排列，**nextPermutation **函数的时间复杂度为 ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29&height=23&id=jDNSm)我们至多执行该函数  ![](https://cdn.nlark.com/yuque/__latex/d02e89c82d457f0c3a1429ad9ce6187c.svg#card=math&code=%5Csmall%20O%28n%21%29&height=23&id=zUKkc) 次，因此总时间复杂度为  ![](https://cdn.nlark.com/yuque/__latex/7726b542705ee8b8a8d69d4ed1a7413b.svg#card=math&code=%5Csmall%20O%28n%C3%97n%21%2Bnlogn%29%3DO%28n%C3%97n%21%29&height=23&id=mvYI5) 

空间复杂度：，注意返回值不计入空间复杂度。

我的代码

public class Solution {
    public boolean nextPermutation(char[] str){
        //1. 找 i<ii
        int i=str.length-2;
        while(i>=0&&str[i]>=str[i+1])i--;
        if(i<0)return false;
        //2. 找 j>i
        int j=str.length-1;
        while(j>=0&&str[j]<=str[i])j--;
        //3. swap(str,i,j)
        swap(str,i,j);
        //4. reverse(ii..end)
        reverse(str,i+1);
        return true;
    }
    public void reverse(char[] str,int i){
        int j=str.length-1;
        while(i<j){
            swap(str,i,j);
            i++;j--;
        }
    }

    public void swap(char[] str,int i,int j){
        char temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res=new ArrayList<>();
        char[]waitString=str.toCharArray();
        Arrays.sort(waitString);
        do{
            res.add(String.valueOf(waitString));
        }while(nextPermutation(waitString));
        return res;
    }
}