2022/07/25 ------ arrangement of strings

Title Description

Arrangement of strings

Their thinking

I looked at the solution of other big guys , There are three main methods ： The idea of backtracking recursion ; The idea of complete arrangement of dictionary order ; Stack based thinking . At present, I only use the idea of full arrangement based on dictionary order to solve problems , Because I haven't understood the other two yet , So coding is a little difficult .
About ： The arrangement process of dictionary order is from the minimum dictionary order , The process of arranging to the maximum lexicographic order . Use the pre suffix method to locate .

Borrow the example of a big man to understand .

Code implementation

The code implementation is as follows .

package cz;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class PermutationP_0725 {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		String s = "bac";
		String[] res=Permutation(s);

	}
	
	public static String [] Permutation(String str) {
    
		//  New return list
		ArrayList<String> res=new ArrayList<>();
		if(str.length()==0||str==null) return (String[]) res.toArray();
		
		//  Convert string to character array 
		char[] chars=str.toCharArray();
		// Get the minimum dictionary order 
		Arrays.sort(chars);
		res.add(String.valueOf(chars));
		int len=chars.length;
		while(true) {
    
			int sindex1=len-1;
			int sindex2;
			while(sindex1>=1 && chars[sindex1-1]>=chars[sindex1]) {
     // The preceding number is greater than the following number ,
				sindex1--;
			}
			if(sindex1==0) {
    // Maximum dictionary order , And then jump out of the loop 
				break;
			}
			sindex2=sindex1;
			while(sindex2<len && chars[sindex2]>chars[sindex1-1]) {
     // Locate the lowest digit greater than the position value to be exchanged ,
				sindex2++;
			}
			swap(chars,sindex1-1,sindex2-1);// Exchange the positions of these two places 
			reverse(chars,sindex1);//sindex1 The remaining mantissa are in reverse order （）
			res.add(String.valueOf(chars));
		}
		
		return (String[]) res.toArray(new String[res.size()]);

	       
	    }
	    
	    public static void reverse(char[] chars,int k){
    
	    	//  Determine the input of outliers 
	    	if(chars==null||chars.length<=k) return;
	    	for(int i=0;i<(chars.length-k)/2;i++) {
    
	    		int left=k+i;
	    		int right=chars.length-1-i;
	    		if(left<=right) {
    
	    			swap(chars,left,right);
	    		}
	    		
	    	}
	    
	    }
	    
	    public static void swap(char[] chars, int i, int j){
    
	    	char temp=chars[i];
	    	chars[i]=chars[j];
	    	chars[j]=temp;
	        
	    }
	

}