This is the 8th day of my participation in Gwen Challenge

The sword refers to Offer 38. Arrangement of strings

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.

The sample

Input: s = "ABC" output: [" ABC ", "acb", "America", "bca", "cab", "cba"]Copy the code

prompt

1 <= length of s <= 8Copy the code

Analysis of personal Ideas

Method one: Backtrack

When it comes to full permutations, it is common to use backtracking to retrieve strings of different permutations by swapping element positions

class Solution {
    private Set<String> set;
    public String[] permutation(String s) {
        // Get an array of characters to facilitate the exchange of elements
        char[] c = s.toCharArray();
        // hash set deweighting
        set = new HashSet<>();
        / / back
        back(c, 0."");
        // Return the result
        String[] ans = new String[set.size()];
        return set.toArray(ans);
    }

    private void back(char[] arr, int index, String str){
        // bounds to add the sorted string to the collection
        if(index == arr.length){
            set.add(str);
            return;
        }

        // Iterate over the following elements, swapping each element with the index element
        for(int i = index; i < arr.length; ++i){
            / / to heavy
            if(i ! = index && arr[i] == arr[index]){continue;
            }
            // Swap elements
            exchange(arr, index, i);
            
            back(arr, index + 1, str + arr[index]);
            / / recoveryexchange(arr, index, i); }}private void exchange(char[] arr, int l, int r){
        charc = arr[l]; arr[l] = arr[r]; arr[r] = c; }}Copy the code

Submit the results

Method two: the next permutation

Repetition can be avoided by sorting the array of characters in an ascending order and then repeating to get the next order that is larger than the current array

For example: 1, 3, 2

  1. From back to front, find the first non-increasing elementiAt this time,i = 0, the current element is1
  2. Go from back to front and find the first onec[i]Big element2
  3. Swap the positions of two elements2, 3, 1
  4. At the same time williThe following elements are reversed2, 1 and 3To get the next array that is closest to the current array value

Official solution: leetcode-cn.com/problems/ne…

class Solution {
    public String[] permutation(String s) {
        List<String> list = new ArrayList<>();
        char[] c = s.toCharArray();
        // Arrange arrays
        Arrays.sort(c);
        do{
            // Add to result set
            list.add(new String(c));
        }while(nextPermutation(c));// Determine if there is another permutation

        // Return the result
        String[] res = new String[list.size()];
        return list.toArray(res);
    }

    private boolean nextPermutation(char[] c){
        // Work backwards to find the first non-increasing element
        int i = c.length - 2;
        while(i >= 0 && c[i] >= c[i + 1]){
            --i;
        }
        / / boundary
        if(i < 0) {return false;
        }
        
        // Find the first element greater than c[I] from back to front
        int j = c.length - 1;
        while(j > i && c[i] >= c[j]){
            --j;
        }
        // Swap the positions of two elements
        swap(c, i, j);
        // Also invert the element after I
        reverse(c, i + 1);
        return true;
    }
    
    // Swap elements
    private void swap(char[] c, int i, int j){
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }
    
    // Array inversion
    private void reverse(char[] c, int i){
        int j = c.length - 1;
        while(i < j){ swap(c, i, j); ++i; --j; }}}Copy the code

Submit the results