《剑指offer》(二十七)--字符串的排序（java）

考点：字符串、动态规划、递归、（分解让复杂问题简单）

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

代码格式

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       
    }
}

本题属于全排列的生成算法，定义：对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。全排列的生成法通常有以下几种：字典序法、递增进位数制法、递减进位数制法、邻位交换法、n进位制法、递归类算法。

解题一-非递归方法（字典序法）

字典序法：按照字典序求下一个排列的算法。
例：字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。当当前的排列54321最大的时候，说明所有的排列都找完了。
于是可以有下面计算下一个排列的算法：
【例】如何得到346987521的下一个
（1）从尾部往前找第一个P(i) < P(i+1)的位置
3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
最终找到6是第一个变小的数字，记录下6的位置i
（2）从i位置往后找到最后一个大于6的数
3 4 6 -> 9 -> 8 -> 7 5 2 1
最终找到7的位置，记录位置为m
（3）交换位置i和m的值
3 4 7 9 8 6 5 2 1
（4）反转i位置后的所有数据
3 4 7 1 2 5 6 8 9
则 347125689 为 346987521 的下一个排列

1.思路
（1）从尾部往前找第一个正序对（array[i] < array[i+1]，因为没有等号，所以可以完美去掉重复的排列）
（2）从i开始向右搜索，找到比array[i]大的字符中最小的那个，记为array[j]
（3）交换array[i]和array[j]
（4）反转i位置后的所有字符
2.代码

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if(str==null || str.length()==0){
            return result;
        }
        //将字符串转为char数组来进行改变字符内容
        char[] array = str.toCharArray();
        //只需将char数组进行排序
        Arrays.sort(array);
        //把chars数组中元素强制转化为字符串类型，并放入result中
        result.add(String.valueOf(array));
        //定义长度
        int len = array.length;
        while(true){
            int i= len-1;
            int j;
            //for循环从尾部往前找第一个正序对
            /*for(int i = length-1;i>=1 && array[i-1]>=array[i]; i--);
            if(i == 0) return "finish";*/
            
            //（1）while循环从尾部往前（向左）找第一个正序对array[i-1]>=array[i]
            while(i>=1 && array[i-1]>=array[i]){
                i--;
            }
            if(i == 0)
                break;
            //（2）while循环从i开始向后（向右）搜索，找到比array[i-1]大的字符中最小的那个，记为array[j]
            j = i;
            while(j<len && array[j]>array[i-1]){
                j++;
            }
            //（3）交换array[i-1]和array[j-1]
            swap(array,i-1,j-1);
            //（4）反转i位置后的所有字符
            reverse(array,i);
 
            result.add(String.valueOf(array));
        }
 
        return result;
    }
    
    private void reverse(char[] chars,int k){
        if(chars==null || chars.length<=k)
            return;
        int len = chars.length;
        for(int i=0;i<(len-k)/2;i++){
            int m = k+i;
            int n = len-1-i;
            if(m<=n){
                swap(chars,m,n);
            }
        }
    }
    //不用方法，直接反转
    /*swap i,j
        for(int a=i+1, b=length-1; a<b;a++,b--){
            tmp = array[a];
            array[a] = array[b];
            array[b] = tmp;
        }
     */
    
   private void swap(char[] chars, int i, int j) {
        // TODO Auto-generated method stub
        if(i != j){
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }
}

解题二-递归方法

1.思路
固定第一个字符，递归取得首位后面的各种字符串组合；再将第一个字符与后面每一个字符交换，同样递归获得其字符串组合；每次递归都是到最后一位时结束，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。

image.png

2.代码

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if(str.length()==0 ||str == null){
            return result;
        }
        PermutationHelper(str.toCharArray(),0,result);
        Collections.sort(result);
        return result;
    }
    private void PermutationHelper(char[] chars,int i,ArrayList<String> result){
        //已经递归到了字符串最后一位，判断集合中有没有这个字符串，没有则加入
        if(i== chars.length-1){
            if(!result.contains(new String(chars))){
                result.add(new String(chars));
                return;
            }
        }else{
            //首次传进来的i为0，代表首位字符
            //依次处理i与i后面的每个字符(索引j)交换
            for(int j=i; j<chars.length; j++){
                swap(chars,i,j);//交换
                PermutationHelper(chars,i+1,result);//继续递归交换后的子串
                swap(chars,i,j);//还原
            }
        }
    }
    private void swap(char[] chars,int i,int j){
        if(i != j){
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }
}

解题三-基于回溯法

1.思路