字符串排序---字典序---鹏-程-万-里

本周我们分享一个获取全排列的算法。这道题当时也是花了蛮久的时间才跟着题解写出来！小白经历了这道题目的“煎熬”之后，就为大家保驾护航，一起轻松拿下此题吧！

我们先来介绍一下此次运用的这道题目的核心思想：字典序排列

字典序

算法示意图

我们先把算法图摆出来给大家参考一下！

整个算法的核心就是按照我们的整体的从小到大的顺序来进行全排列，比如：123-->132-->213-->231-->312-->321

完成这段全排列流程的步骤主要有以下几步

需要对给定的序列进行排序，得到一个有序数组（一般认为是从小到大的）从右向左开始寻找一个第一个A[i]<A[i+1]。继续从左向右寻找都一个满足A[i]>A[j]关系的元素，交换A[i]和A[j]。对A[i]之后的元素进行翻转（也就是从小到大排序），得到一个新的排列。重复2~4当无法再进行找到满足A[i]<A[i+1]关系的数据时，整个全排列便已经被全部找完了。

经过上面的步骤，我们每次得到的排列组合也将会是一个从小到大排序的全排列组合！

字符串的排列

《剑指offer》--------- 字符串的排列 题目描述

题目描述

简言之就是找到一个给定字符串的全排列。

1、解决思路

根据我们上面介绍的字典序排列算法，就可以轻松的解决我们此次的问题啦！

2、代码实现import java.util.ArrayList; import java.util.Arrays; //字典序 public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> ans = new ArrayList<>(); if(str == null || str.length() == 0) return ans; if(str.length() == 1) { ans.add(str); return ans; } char[] ch = str.toCharArray(); Arrays.sort(ch); String s = new String(ch); ans.add(str);//此处是为了防止重复的字符串 while(true){ s = dic(s); if(!s.equals("stop")){ ans.add(s); }else{ break; } } return ans; } private String dic(String s){ char[] ch = s.toCharArray(); int len = ch.length; int left = len - 2; //从右向左寻找第一个小于右边元素的索引 for(;left >=0;left--){ if(ch[left] < ch[left +1]){ break; } } //判断是否已经越界 if(left == -1){ return "stop"; } //从右边寻找大于left的最小元素 int right = len - 1; for(;right > left ; right--){ if(ch[left] < ch[right]){ break; } } //交换left和right位置 char temp = ch[left]; ch[left] = ch[right]; ch[right] = temp; //翻转left后面的字符串 for(int a = left+1,b=len-1;a < b ;a++,b--){ temp = ch[a]; ch[a] = ch[b]; ch[b] = temp; } return new String(ch); } } ---来自腾讯云社区的---鹏-程-万-里