题目: 输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
class Solution { List<String> list = new LinkedList<>(); char[] c; public String[] permutation(String s) { if(s == null){ return new String[0]; } c = s.toCharArray(); //将字符串转换为字节数组 dfs(0); return list.toArray(new String[list.size()]); //toArray(T[] a),返回指定类型T的数组,比如这里返回的就是指定的String[]类型的数组。 } void dfs(int k){ if(k == c.length-1){ //递归了c.length-1次,说明前面k-1个元素依次固定,最后一个元素填坑即可,整个c数组排序完毕,得到一个排序后的字符串。 list.add(String.valueOf(c)); return; } HashSet<Character> set = new HashSet<>(); for(int i = k;i < c.length;i++){ /*使用set不会存储相同元素的个性,对数组元素进行剪枝,当出现重复字符,如aab的情况时,对于c[0],c[1]的交换是无意义的, 得到的结果相同,如果不进行剪枝,会得到成对的aab,aab,aba,aba,baa,baa这样的结果*/ if(set.contains(c[i])){ continue; } set.add(c[i]); /* 首元素k依次与其它元素交换,使数组中的其它元素轮流充当首元素。如[a,b,c],依次交换得到[b,a,c], [c,b,a],其中a,b,c依次充当首元素。 */ swap(c,i,k); /* 对于第i位元素同样将其与右边剩余元素依次交换,以达到轮流固定第i位元素的效果。如对于 [a,b,c],第一步固定[a,],然后dfs(k+1)依次交换固定b,c得到,[a,b,c],[a,c,b]。对于c.length个元素,需逐层 固定第i位元素,并将其与右边的元素依次进行交换。 */ dfs(k+1); swap(c,k,i); //上面一次循环交换完毕得到数组c后,需要交换回来位下次交换做准备。 } } void swap(char[] c,int i,int j){ char b = c[i]; c[i] = c[j]; c[j] = b; } }