leetcode sword finger Offer 38 Arrangement of strings

Sword finger Offer 38 Arrangement of strings

Title Description

Enter a string and print out all the arrangements of characters in the string.

You can return this string array in any order, but there can be no duplicate elements in it.

Example:

Input: s = "abc"
Output:["abc","acb","bac","bca","cab","cba"]

Restrictions:

1 <= s Length of <= 8

Idea 1:

In fact, it is the full arrangement of all characters in the String, but if there are repeated characters in the String, some of the arrangement may be repeated, so first save the results in a set, use HashSet to de duplicate the results, and finally convert the results into String []

 1 class Solution {
 2 
 3     public String[] permutation(String s) {
 4         // One exists first set In the collection because set Sets can de duplicate the results
 5         HashSet<String> res = new HashSet<>();
 6         StringBuilder sb = new StringBuilder(s);
 7         // Recursive generation of Full Permutation
 8         helpPermutation(sb, 0, sb.length(), res);
 9         // Convert the result set into an array and return
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 Indicates the number of elements that have been arranged
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         // Recursive order finding k Characters to n Full arrangement of characters
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 execution time: 36 MS > 27.94%, memory consumption: 43.2 MB > 82.75%

Complexity analysis:

Spatial complexity: according to the full arrangement, a total of n! Results, so the time complexity is O(n!)

Space complexity: all results are stored in a HastSet temporary set, and the maximum space of this part is O(n!), In addition, the depth of recursive stack is O(n), so the overall space complexity is O(n!)

Train of thought II

Prune in the process of generating the result set. When the same character appears in a position during the exchange process, it indicates that the arrangement is repeated. You can skip this arrangement because it has been generated before

 1 class Solution {
 2 
 3     public String[] permutation(String s) {
 4         // One exists first set In the collection because set Sets can de duplicate the results
 5         ArrayList<String> res = new ArrayList<>();
 6         StringBuilder sb = new StringBuilder(s);
 7         // Recursive generation of Full Permutation
 8         helpPermutation(sb, 0, sb.length(), res);
 9         // Convert the result set into an array and return
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 Indicates the number of elements that have been arranged
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         // Recursive order finding k Characters to n Full arrangement of characters
28         HashSet<Character> set = new HashSet<>();   // Record the second k If there are repeated characters, skip directly
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 execution time: 15 ms > 50.80%, memory consumption: 43.2 MB > 83.84%. It can be seen that the time is more than twice as fast

Complexity analysis:

Spatial complexity: according to the full arrangement, a total of n! Results, so the time complexity is O(n!)

Space complexity: all results are stored in an ArrayList temporary set, and the maximum space of this part is O(n!), In addition, the depth of recursive stack is O(n), and the maximum number of elements in HashSet is O(n + (n-1) + (n + 2) ++ 1) = O(n2), so the overall spatial complexity is O(n!)

Tags: Algorithm

Posted by alex_savin on Fri, 13 May 2022 11:45:28 +0300