Leetcode – Offer [38] – Arrangement of strings

[Blog link]

A path to learning at 🐔

The nuggets home page

[B].

Enter a string and print out all permutations of the characters in the string. You can return this array of strings in any order, but no repeating elements. Example: Input: S = "ABC" Output: [" ABC "," ACB "," BAC "," BCA "," CAB "," CBA "] Limit: 1 <= length of S <= 8 Related Topics Backtracking algorithm 👍 297 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: violence + recursion + backtracking

• One selection state per string,
• Recursive string concatenation by backtracking
• And then we put it in a set and we return a String array that doesn’t contain the same elements

class Solution{
	Set<String> set = new HashSet<>();

        public String[] permutation(String s) {

            for (int i = 0; i < s.length(); i++) {
                boolean[] vis = new boolean[s.length()];
                vis[i] = true;
                String temp = s.substring(i, i + 1);

                arrangeS(s, vis, temp);
            }
            return set.toArray(new String[0]);
        }


        // recursive processing
        public void arrangeS(String s, boolean[] vis, String init) {
            if (init.length() == s.length()){
                set.add(init);
                return;
            }
            for (int i = 0; i < s.length(); i++) {
                String temp = init;
                if(! vis[i]) { temp += s.substring(i, i +1);
                    vis[i] = true;
                    arrangeS(s,vis,temp);
                    vis[i] = false; }}}}Copy the code

Time complexity O(n!)

Idea 2: Optimization Idea 1 (Map storage)

• Because they have the same elements in them, some of the branches don’t need to be repeated recursively
• You can use a map to record traversal elements

class Solution {
Set<String> set = new HashSet<>();

        public String[] permutation(String s) {
            Map<String, Integer> map = new HashMap<>();
            for (char c : s.toCharArray()
            ) {
                map.put(String.valueOf(c), map.getOrDefault(String.valueOf(c), 0) + 1);
            }
            arrangeS(s,map,"");
            return set.toArray(new String[0]);
        }

        public void arrangeS(String s, Map
       
         map, String init)
       ,> {
            if (init.length() == s.length()) {
                set.add(init);
                return;
            }
            for (String temp : map.keySet()
            ) {
                String str=init;
                if(map.get(temp) ! =0) {
                    map.put(temp, map.get(temp) - 1);
                    arrangeS(s, map, str + temp);
                    map.put(temp, map.get(temp) + 1); }}}}Copy the code

Time complexity O(n!)