题解 | #字符串的排列#
字符串的排列
http://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7
递归函数功能:
收入 当前得到的字符串+剩余的可取字符集
操作 保存这两个参数,以便回溯
遍历可取字符集
--1.将该字符取出加入到当前字符串,把新的字符串和可取集传下去(子递归)
--2.从上一个递归返回后,把此时的字符串和可取集回溯到初值
主要思路:循环递归、复制初值以回溯、利用set消重(最开始用set接收,后面遍历取出来的时候虽然结果全都有,但是hashset的顺序不一样,所以这里仅用set作判断,可放入则加入结果列表,不可放入则是重复,丢掉)
import java.util.*; //用模拟取出换实现 递归 回溯 消重 *千万要搞清楚复制和引用的区别,回溯的断点这里用引用又卡了两小时,吐血 public class Solution { static HashSet Fin1=new HashSet(); static ArrayList Fin=new ArrayList(); public ArrayList Permutation(String str) { //把字符串转化为ArryList able char[] x = str.toCharArray(); ArrayList able = new ArrayList(); for (int i = 0; i <=x.length-1 ; i++) { able.add(x[i]); } //开一个空的起始StringBuffer StringBuffer start=new StringBuffer(); //前者表示当前字符串,后者表示剩余可用字符集 fun(start,able); return Fin; } public void fun(StringBuffer result,ArrayList able){ //接收当前字符串 开res副本接收result、able1接收able,且以便回溯 StringBuffer res=new StringBuffer(result); ArrayList able1=new ArrayList(able); // if(able.size()==0){ //尝试把结果字符串放入set结果集 if(Fin1.add(res.toString())){ Fin.add(res.toString()); }; } if(able.size()!=0) { //从可用字符集中取一个加到当前字符串 for (int i = 0; i <=able.size()-1 ; i++){ res.append(able.get(i)); able1.remove(i); fun(res, able1); //这里要回溯,恢复到刚传入的result和able值 able1=new ArrayList(able); res=new StringBuffer(result); } } } }