String full permutation algorithm_ C # version_ Sword finger OFFER

Title Description

Title Description
Enter a string of length n and print out all the permutations of characters in the string. You can return this string array in any order.
For example, if you input string ABC, all strings ABC,ACB,BAC,BCA,CBA and CAB that can be arranged by characters a, B and C will be output.
Data range: n < 10N < 10
Requirement: space complexity O(n!)O(n!)， Time complexity O(n!)O(n!)
Input Description: enter a string with a length of no more than 10, and the characters only include uppercase and lowercase letters.

​

thinking

Obviously, this topic is called recursive thinking. Fix one character, exchange with the remaining characters in turn, and then fix the next. The idea is similar to arrangement
Firstly, the string is divided into two parts, one is the fixed string for exchange, and the other is the exchange string waiting for exchange. For the convenience of explanation, the characters in the fixed string are called fixed characters, and the characters in the exchange string are called exchange characters.
Then the recursive order is as follows:

1. Fix the first character and exchange it with the rest of the exchange string substr in turn
2. Treat substr as the first string, fix the first character of substr, operate 1 until the length of substr is 0, and end the recursion
3. After the first fixed character is used, start fixing the second character and exchange character values with the remaining string substr in turn
4. Repeat the above steps until all characters are fixed

At this point, there will be the problem of duplicate strings. If the fixed character is the same as the exchange character, it is a white exchange. At this time, you can set different settings before switching.
But there will still be repeated problems:

For example, a b1 b2,
According to the idea,
first round
Fixed a
After one exchange, B1 a B2 is obtained. After substr (a, B2), b1 b2 a is obtained. (step 2)
a b1 b2 is exchanged for the second time to get b2 b1 a, which is repeated at this time

At this time, the repetition problem occurs because after entering recursion, substr can be regarded as an independent string, and the previous fixed string cannot affect the exchange string generated by substr. Obviously, if the substr string has the same number of letters, it will produce repeated arrangement.
In order to solve this problem, cut off the substr with all the same letters in advance.
Judge whether the string between the current exchange character and the fixed character (called intermediate string) has repeated characters. If so, cancel the exchange.

For example, a b1 c b2 d,
According to the idea,
First round fixing a,
For the first time, b1 a c b2,
substr (a,c,b2) always gets the exchange string b2,c,a
After a and b2 are exchanged, b2 B1, C, a is obtained. After this string enters recursion, substr(b1,c,a) will certainly produce repeated arrangement

using System.Collections.Generic;
using System;
class Solution
{
    public List<string> Permutation(string str)
    {
        // write code here
        List<string> res = new List<string>();
        if(str.Length==0)return res;
        recursion(0,str,ref res);
        return res;
    }
    public void recursion(int fixedIdx,string str,ref List<string> res)
    {
        // write code here
        //Note that string is not modifiable, so it should be converted to string array
        char [] newstr = str.ToCharArray();
        res.Add(str); //Add initial string
        int curIdx;
        while(fixedIdx<str.Length)
        {   //Fixed characters advance in turn
            for(curIdx=fixedIdx+1;curIdx<str.Length;curIdx++)
                {
                   if(is_swap(fixedIdx,curIdx,newstr)){
                        swap(fixedIdx,curIdx,ref newstr);   //exchange
                        recursion(fixedIdx+1,new string(newstr),ref res); //Recursion starts after the position determined by this string
                        newstr=str.ToCharArray(); //restore
                    }
                }
            fixedIdx++;
        }
    }
     //Prevent repetition with the previous exchange string. If the recursive string has the same number of letters, the repeated arrangement will be output
     //Ensure that similar strings are output only once
    public bool is_swap(int fixedIdx,int curIdx,char[] newstr)
    {
        int idx=curIdx-1;  //Compare whether the middle string has equal characters in turn. If it returns false, skip this round of exchange
        while(idx>=fixedIdx)
        {
            if(newstr[idx]==newstr[curIdx])
                return false;
            idx--;
        }
        return true;
    }
    //exchange
    public void swap(int fixedIdx,int idx,ref char[] substr)
    {
        char tmp=substr[fixedIdx];
        substr[fixedIdx]=substr[idx];
        substr[idx]=tmp;
    }
}