leetcode 剑指 Offer 38. 字符串的排列

剑指 Offer 38. 字符串的排列

题目描述

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

思路一：

其实就是字符串中所有字符的全排列，但是如果字符串中有重复字符的话，部分排列可能会重复，所以要先把结果都存在一个set中，利用HashSet对结果进行去重，最后将结果转换成String[]即可

 1 class Solution {
 2 
 3     public String[] permutation(String s) {
 4         // 先存在一个set集合中，因为set集合可以对结果去重
 5         HashSet<String> res = new HashSet<>();
 6         StringBuilder sb = new StringBuilder(s);
 7         // 递归生成全排列
 8         helpPermutation(sb, 0, sb.length(), res);
 9         // 把结果集合转换成数组后返回
10         return res.toArray(new String[0]);
11 
12     }
13 
14     public void swap(StringBuilder sb, int i, int j){
15         char temp = sb.charAt(i);
16         sb.setCharAt(i, sb.charAt(j));
17         sb.setCharAt(j, temp);
18     }
19 
20     // k表示已经排列到第几个元素了
21     public void helpPermutation(StringBuilder sb, int k, int n, HashSet<String> res){
22         if(k >= n-1){
23             res.add(sb.toString());
24             return;
25         }
26 
27         // 递归求第k个字符到第n个字符的全排列
28         for(int i = k; i < n; i++){
29             swap(sb, k, i);
30             helpPermutation(sb, k+1, n, res);
31             swap(sb, k, i);
32         }
33     }
34 }

leetcode执行用时：36 ms > 27.94%, 内存消耗：43.2 MB > 82.75%

复杂度分析：

空间复杂度：根据全排列一共会产生n!个结果，所以时间复杂度为O(n!)

空间复杂度：把所有结果都存在了一个HastSet临时集合中，这部分的最大空间为O(n!), 另外递归栈的深度为O(n), 所以总的来说空间复杂度为O(n!)

思路二

在产生结果集的过程中进行剪枝，当一个位置在交换的过程中出现了同一个字符，说明这个排列重复了，可以跳过此次排列，因为这个排列之前已经生成过

 1 class Solution {
 2 
 3     public String[] permutation(String s) {
 4         // 先存在一个set集合中，因为set集合可以对结果去重
 5         ArrayList<String> res = new ArrayList<>();
 6         StringBuilder sb = new StringBuilder(s);
 7         // 递归生成全排列
 8         helpPermutation(sb, 0, sb.length(), res);
 9         // 把结果集合转换成数组后返回
10         return res.toArray(new String[0]);
11 
12     }
13 
14     public void swap(StringBuilder sb, int i, int j){
15         char temp = sb.charAt(i);
16         sb.setCharAt(i, sb.charAt(j));
17         sb.setCharAt(j, temp);
18     }
19 
20     // k表示已经排列到第几个元素了
21     public void helpPermutation(StringBuilder sb, int k, int n, ArrayList<String> res){
22         if(k >= n-1){
23             res.add(sb.toString());
24             return;
25         }
26 
27         // 递归求第k个字符到第n个字符的全排列
28         HashSet<Character> set = new HashSet<>();   // 记录下第k个位置的字符，如果有重复直接跳过
29         for(int i = k; i < n; i++){
30             if(set.contains(sb.charAt(i))){
31                 continue;
32             }
33             set.add(sb.charAt(i));
34             swap(sb, k, i);
35             helpPermutation(sb, k+1, n, res);
36             swap(sb, k, i);
37         }
38     }
39 }

leetcode 执行用时：15 ms > 50.80%, 内存消耗：43.2 MB > 83.84%, 可以看到，时间上快了一倍多

复杂度分析：

空间复杂度：根据全排列一共会产生n!个结果，所以时间复杂度为O(n!)

空间复杂度：把所有结果都存在了一个ArrayList 临时集合中，这部分的最大空间为O(n!), 另外递归栈的深度为O(n), HashSet中的元素个数最大为O(n + (n-1) + (n+2) + ... + 1) = O(n²), 所以总的来说空间复杂度为O(n!)