This is the 22nd day of my participation in Gwen Challenge

Topic describes

This is the index Offer 38 on LeetCode. It’s a string arrangement of medium difficulty.

Tag: “string”, “backtracking algorithm”

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", "America", "bca", "cab", "cba"]Copy the code

Limitations:

  • 1 <= length of s <= 8

Fundamental analysis

By definition, we need to return all non-repeating permutation strings.

This kind of problem is usually done using DFS to decide what character to fill in a particular bit of the current string.

Design the following DFS functions:

/** * cs: the original string * u: the current decision to the target string * cur: the current target string */
void dfs(char[] cs, int u, String cur);
Copy the code

There are two ways to remove weight:

  1. useSetAchieve weight reduction;
  2. Sort the original string first, and then ensure that the same character is passed to the same destination location only once.

Backtrace (Set deduplicate)

Using HashSet to implement de-duplication is quite simple, just don’t worry about de-duplication.

Decide directly which character is taken from which part of the target string, and use a Boolean array to record which characters are used.

Code:

class Solution {
    int N = 10;
    Set<String> set = new HashSet<>();
    boolean[] vis = new boolean[N];
    public String[] permutation(String s) {
        char[] cs = s.toCharArray();
        dfs(cs, 0."");
        String[] ans = new String[set.size()];
        int idx = 0;
        for (String str : set) ans[idx++] = str;
        return ans;
    }
    void dfs(char[] cs, int u, String cur) {
        int n = cs.length;
        if (u == n) {
            set.add(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(! vis[i]) { vis[i] =true;
                dfs(cs, u + 1, cur + String.valueOf(cs[i]));
                vis[i] = false; }}}}Copy the code
  • Time complexity: O(n∗n!) O(n * n!) O (n ∗ n!)
  • Space complexity: O(n)O(n)O(n)

Backtracking (sort de-duplication)

To achieve de-duplication through preprocessing, you need to “sort the original string first and then ensure that the same character is passed to the same destination only once.”

Specifically, we can skip cs[i-1] = cs[I] when “deciding the uuu position of the target string”. At the same time, in order to ensure that this action does not affect the following position decision, we need to take advantage of the same target position will be “backtracked” feature, add a! Judgment of VIS [I-1].

Such as… xxx… The action of using the character x to decide the uuu position of the target string only happens once, ensuring that the exact same branch cannot be expanded more than once in the “recursion tree”.

This kind of de-duplication occurs in many ways, and in fact it doesn’t just apply to permutation problems.

Its essence is to skip the “identical state” nodes in the recursion tree, so as to achieve de-duplication.

In this case, “identical state” means that the current partial result is the same as curcurcur, and the remaining set of characters is the same.

Code:

class Solution {
    int N = 10;
    List<String> list = new ArrayList<>();
    boolean[] vis = new boolean[N];
    public String[] permutation(String s) {
        char[] cs = s.toCharArray();
        Arrays.sort(cs);
        dfs(cs, 0."");
        String[] ans = new String[list.size()];
        int idx = 0;
        for (String str : list) ans[idx++] = str;
        return ans;
    }
    void dfs(char[] cs, int u, String cur) {
        int n = cs.length;
        if (u == n) {
            list.add(cur);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (i > 0 && !vis[i - 1] && cs[i] == cs[i - 1]) continue;
            if(! vis[i]) { vis[i] =true;
                dfs(cs, u + 1, cur + String.valueOf(cs[i]));
                vis[i] = false; }}}}Copy the code
  • Time complexity: O(n∗n!) O(n * n!) O (n ∗ n!)
  • Space complexity: O(n)O(n)O(n)

The last

This is the first Offer of 38 articles in our series of “Brush through LeetCode”. The series started on January 21, 01/01, and there are 1916 questions in LeetCode by the start date, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.