剑指Offer-字符串的排列

比眉伴天荒 2022-02-22 13:08 180阅读 0赞

## 题目描述 ##

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

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

解题思路—**递归：基于回溯法思想**：**核心思想就是固定第一个字符，递归取得首位后面的各种字符串组合；再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合。如果遇到重复值**，比如说当前首位字母为a，下一位字母也为a，则**不交换**！因为交换了还是一样的。怎样判断之前的字符串中有没有存在当前字母呢，使用**HashSet**是一个非常好的选择，可以自动判断当前的Set中有没有重复。  
使用某位大佬给出的**图解**：  
![回溯法][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]  
解题思路—**字典序排列方法**：这个方法的核心思想是**全排序**！需要注意的是两个概念：**前缀和后缀**。怎么做全排序，需要找到数列的顺序，即相邻两个数列**要有尽可能长的共同前缀，将变化限制在尽可能短的后缀上**，最后生成一系列按字典序排的数列。

> 看到有大佬写了个很好的例子：  
> \[例\] 839647521是1–9的排列，排列可以得到最大的数列是987654321，最小的数列是123456789。  
> 从右向左扫描数列是递增的，所以排序顺序为123456789 ~ 987654321，那么如何寻找排序数列的下一个呢再举个例子：  
> \[例\] 如何得到346987521的下一个
> 
> 1.  从尾部往前找第一个P(i-1) < P(i)的位置 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1 最终找到6是第一个变小的数字，记录下6的位置i-1
> 2.  从i位置往后找到最后一个大于6的数 3 4 6 -> 9 -> 8 -> 7 5 2 1 最终找到7的位置，记录位置为m
> 3.  交换位置i-1和m的值 3 4 7 9 8 6 5 2 1
> 4.  倒序i-1位置后的所有数据 3 4 7 1 2 5 6 8 9
> 
> 则347125689为346987521的下一个排列数列

解题思路—**基于堆栈**：看到有一个大佬用堆栈进行了排序，这个方法很巧妙，代码比较精简，也**不用sort**，使用了**TreeSet自动排序**，可以学习借鉴一下！

## Java解题—递归 ##

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashSet;
    public class Solution {
        public ArrayList<String> Permutation(String str) {
            ArrayList<String> result = new ArrayList<>();
            if(str!=null && str.length()>0){
                Ranged(str.toCharArray(), 0, result);
                Collections.sort(result);
            }
            return result;
        }
        
        public void Ranged(char[] chars, int i, ArrayList<String> result){
            if((chars.length-1)==i)
                result.add(String.valueOf(chars));
            else{
                HashSet<Character> charSet = new HashSet<Character>();
                for(int j=i;j<chars.length;j++){
                    if(!charSet.contains(chars[j])){
                        charSet.add(chars[j]);
                        swap(chars, i, j);
                        Ranged(chars, i+1, result);
                        swap(chars, i, j); // 第一次swap的复位
                    }
                }
            }
        }
    
        public void swap(char[] chars, int i, int j){
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }

## Java解题—字典序排列方法 ##

import java.util.ArrayList;
    import java.util.Arrays;
    public class Solution {
        public ArrayList<String> Permutation(String str) {
           ArrayList<String> list = new ArrayList<String>();
            if(str==null || str.length()==0){
                return list;
            }
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            list.add(String.valueOf(chars));
            int len = chars.length;
            while(true){
                int lIndex = len-1;
                int rIndex;
                while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                    lIndex--;
                }
                if(lIndex == 0)
                    break;
                rIndex = lIndex;
                while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                    rIndex++;
                }// 比rIndex大的数
                swap(chars,lIndex-1,rIndex-1);// chars后半部分是递减的，所以要rIndex-1
                reverse(chars,lIndex); // 后半部分数组倒序
     
                list.add(String.valueOf(chars));
            }
            return list;
        }
        
        public 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);
            }
        }
        
        public void swap(char[] chars, int i, int j){
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
        }
    }

## Java解题—基于堆栈 ##

import java.util.ArrayList;
    import java.util.TreeSet;
    import java.util.Stack;
    public class Solution {
        public ArrayList<String> Permutation(String str) {
            TreeSet<String> tree = new TreeSet<>();
            Stack<String[]> stack = new Stack<>();
            ArrayList<String> results = new ArrayList<>();
            stack.push(new String[]{str, ""});  // stackStr, oldStr
    
            while(!stack.isEmpty()){
                String[] popStrs = stack.pop();
                String oldStr = popStrs[1];
                String stackStr = popStrs[0];
                for(int i=stackStr.length()-1;i>=0;i--){
                    //  压入i
                    String[] strs = new String[]{stackStr.substring(0,i)+stackStr.substring(i+1),oldStr+stackStr.substring(i,i+1)};
                    if(strs[0].length()==0)
                        tree.add(strs[1]);
                    else
                        stack.push(strs);
                }
            }
            for(String s:tree)
                results.add(s);
            return results;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220222/5a2183cc621944eb9f3b30c00128c228.png