字符串的排列

题目描述思路实现

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

就是暴力枚举的思想，递归+回溯 定义两个辅助函数：一个递归函数，一个交换数组元素函数

递归函数：从字符数组的第一个元素开始，自己和自己交换有哪些情况？自己和自己下一个交换有哪些情况？…直到自己和最后一个元素交换有哪些情况？ 每次找到一种情况后，必须回溯到上一步，再去其他分路找找看有什么其他可能 递归出口：最后一个元素也和自己交换完了

找到一种组合后，把字符数组转换成字符串，加入结果集合中，但是需要先判断这些组合是否重复（利用集合的contais方法即可）

实现

import java.util.ArrayList; import java.util.Collections; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> res=new ArrayList<>(); //存放结果的集合 //特殊情况：空串 if(str.length()==0) return res; //先把字符串转字符数组 char[] c=str.toCharArray(); fun(c,res,0); //从第一个元素开始遍历和交换 //对得到的排列结果进行字母顺序排序：直接调用sort方法 Collections.sort(res); return res; } //辅助函数：递归+回溯（即暴力列举所有结果，并把结果加入list中） //参数：待遍历的字符数组，存放结果的集合，当前遍历到的字符数组下标 public void fun(char[] c,ArrayList<String> list,int i){ //递归出口：已经遍历到数组最后一个元素 if(i==c.length-1){ //先判断下得到的所有字符排列组合是否重复，不重复再加入到list中 if(!list.contains(String.valueOf(c))){ //得到的排列组合是字符串,把字符数组转换成字符串 list.add(String.valueOf(c)); } } //开始遍历（每找到一种组合，要回溯到上一步） else{ for(int j=i;j<c.length;j++){ swap(c,i,j); fun(c,list,i+1); //递归 swap(c,i,j); //回溯到上一步 } } } //辅助函数：交换数组两个下标的元素 public void swap(char[] c,int i,int j){ char t=c[i]; c[i]=c[j]; c[j]=t; } }