剑指 Offer 38: 字符串的排列

[songyy5517]

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

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

分析 这道题本质上是考察字符串的全排列，我们可以使用递归的方法来解决问题。

[songyy5517]

思路：将字符串看成第一个字符和剩下的字符串，递归处理

1. 异常处理；
2. 定义相关变量：全局列表和字符数组（Arrays.copyOf or str.toCharArray()）；
3. 定义递归函数：固定字符串前len位字符，对之后的串进行全排列： （1）递归出口：若len到达原字符串长度，则将字符串保存到列表中，并返回； （2）定义HashSet集合处理重复字符的情况； （3）通过HashSet判断len之后的字符与len位置的字符是否重复：
   • 若字符不重复，则交换二者位置对之后的字符串进行递归全排列，最后再交换回来；
   • 否则，直接跳过进入下一次循环。
4. 在主函数中调用递归函数；
5. 将列表转换成字符串数组，并返回。

复杂度分析：

• 时间复杂度 $O(N!N)$ ： N为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 $N×(N−1)×(N−2)…×2×1$ ，即复杂度为 $O(N!)$；此外，在第len次递归中，len位置上的字符选择有 $N-len$ 种，本次递归内HashSet的容量是 $N-len$ ，判断当前字符是否在HashSet内不需要遍历HashSet中的元素，查找的时间复杂度是 $O(1)$ 。递归出口中字符串拼接操作new String(char[]) 使用了 $O(N)$ 的时间；因此总体时间复杂度为 $O(N!N)$ 。

• 空间复杂度 $O(N^2)$ ： 全排列的递归深度为 $N$ ，系统累计使用栈空间大小为 $O(N)$ ；递归中辅助 Set 累计存储的字符数量最多为 $N+(N−1)+...+2+1=(N+1)N/2$，每层递归中HashSet的平均容量为 $N/2$，因此共占用 $O(N^2)$ 的额外空间。

[songyy5517]

import java.util.*;

public class Solution {
    ArrayList<String> res = new ArrayList();
    public ArrayList<String> Permutation (String str) {
        // write code here
        // 1. 异常处理
        if (str == null || str.length() == 0)
            return new ArrayList();

        // 2. 定义相关变量
        char[] str_1 = str.toCharArray();

        // 3. 递归全排列 
        sortString(str_1, 0);

        return res;
    }

    // 递归：固定字符串str的前len个字符，对之后的串进行全排列
    void sortString(char[] str, int len){
        // 递归出口
        if (len == str.length - 1){
            res.add(new String(str));
            return ;
        }

        // 对当前位置进行排列
        HashSet<Character> hs = new HashSet();
        for (int i = len; i < str.length; i++){
            if (!hs.contains(str[i])){
                hs.add(str[i]);
                char temp = str[i];
                str[i] = str[len];
                str[len] = temp;

                sortString(str, len + 1);

                temp = str[i];
                str[i] = str[len];
                str[len] = temp;
            }
        }
    }
}

[songyy5517]

2023/2/3

1. 为什么要交换回来？若全排列完之后，i位置的字符变了呢？
   • 复原数组（从最内层向外看）：保证每一次新的for循环，seq都和第一次for循环的值一样（感觉还是没有完全弄懂，不过没关系弄不懂也很正常，慢慢来~）

2023/11/29

1. 由于递归的性质，元素之间的交换也是从内向外的，因此不会导致顺序错位。
2. 通过HashSet判断当前字符是否重复（作为全排列的首字符），时间复杂度不能忽略这个步骤。

2024/3/23

1. 时间复杂度 & 空间复杂度；
2. HashSet检索元素的时间复杂度为 $O(1)$ ；