基于回溯法思想:
import java.util.ArrayList; import java.util.Collections; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> list = new ArrayList<String>(); if(str==null) return list; char[] chArr=str.toCharArray(); if(chArr.length==0) return list; fullSort(chArr,0,list); Collections.sort(list); return list; } private void fullSort(char[] chArr,int begin,ArrayList<String> list){ int length=chArr.length; if(begin==chArr.length-1){
//如果字符串中有两个元素相同,会出现相同的全排列,所以需要去重 if(!list.contains(String.valueOf(chArr))) list.add(String.valueOf(chArr)); return; } for(int index=begin; index<length; index++){ //交换数组首元素和index下标处的元素 char temp=chArr[index]; chArr[index]=chArr[begin]; chArr[begin]=temp; //对每个交换后的数组,首元素后移一位,然后执行相同的操作 fullSort(chArr, begin+1, list); //恢复数组为原来的形式,需要再次交换首元素和index下标处的元素 temp=chArr[index]; chArr[index]=chArr[begin]; chArr[begin]=temp; } } }