2022/07/25------字符串的排列

题目描述

字符串的排列

解题思路

我看了一下其他大佬的解法，主要是三种方法：回溯递归的思想；字典序全排列的思想；基于堆栈的思想。我这里目前只使用了基于字典序全排的思想解题，因为其他两种自己还没理解透，所以代码编写有些困难。
大概讲一下：字典序的排列过程是从最小字典序，排列到最大字典序的过程。使用前后缀的方法进行定位。

借用一位大佬的例子进行理解。

代码实现

代码实现如下。

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) {
    
		// 新建返回list
		ArrayList<String> res=new ArrayList<>();
		if(str.length()==0||str==null) return (String[]) res.toArray();
		
		// 将字符串转化成字符数组
		char[] chars=str.toCharArray();
		//得到最小字典序
		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]) {
     //前面数字大于后面数字，
				sindex1--;
			}
			if(sindex1==0) {
    //最大字典序，则跳出循环
				break;
			}
			sindex2=sindex1;
			while(sindex2<len && chars[sindex2]>chars[sindex1-1]) {
     //定位大于要交换位置值的最低位数，
				sindex2++;
			}
			swap(chars,sindex1-1,sindex2-1);//交换这两处的位置
			reverse(chars,sindex1);//sindex1剩下的尾数做倒序（）
			res.add(String.valueOf(chars));
		}
		
		return (String[]) res.toArray(new String[res.size()]);

	       
	    }
	    
	    public static void reverse(char[] chars,int k){
    
	    	// 判断异常值的输入
	    	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;
	        
	    }
	

}