题目:字符串的排列
要求:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。(输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。)
很典型的一道回溯算法的题目
1 import java.util.List; 2 import java.util.ArrayList; 3 import java.util.Collections; 4 public class Solution { 5 public ArrayList<String> Permutation(String str) { 6 List<String> result = new ArrayList<String>(); 7 //考虑特殊情况,并做强制性转换 8 if(str.length()==0) return (ArrayList)result; 9 function(str.toCharArray(),result,0); 10 //将所有结果进行字典排序 11 Collections.sort(result); 12 return (ArrayList)result; 13 } 14 public void function(char [] chr,List<String> temp,int i){ 15 //在所有已经添加进来的结果中,判断是否有重复的,无重复的才能添加 16 if(i==chr.length-1){ 17 if(!temp.contains(new String(chr))){ 18 temp.add(new String(chr)); 19 return; 20 } 21 }else{ 22 //回溯法正式开始,循环+递归 23 for(int j=i;j<chr.length;j++){ 24 swap(chr,i,j); 25 function(chr,temp,i+1); 26 //先把第一个字符与后面任意一个字符交换，交换后要还原到交换前的状态，否则会影响之后的循环 27 swap(chr,i,j); 28 } 29 } 30 } 31 32 //交换字符串函数,这个很容易理解 33 public void swap(char[] chr,int i,int j){ 34 if(i!=j){ 35 char m = chr[i]; 36 chr[i]= chr[j]; 37 chr[j]= m; 38 } 39 } 40 }
解释
bug1: 第6行 List<String> result = new ArrayList<String>();不能写成 ArrayList<String> result = new ArrayList<String>();的形式,
原因1:Collections.sort()函数中,需要放List,如果是ArrayList显然就不能用了
原因2: <图片转自https://www.cnblogs.com/PeterZhang1520389703/p/6763170.html>
bug2: 第9行 function(str.toCharArray(),result,0); 将字符串String转换成char数组,需要 String.toCharArray()
bug3: 第17/18行 if(!temp.contains(new String(chr))){ temp.add(new String(chr)); new String(chr)
在回溯中,每一次最终结果都是char数组,必须要转换成String才能保存进去啊,有两种方法
String str = new String(data); 和 String.valueOf(char[] chr)
bug4: 在草稿纸上写下回溯的过程,发现它是循环中带着递归,
无注释版本
1 import java.util.List; 2 import java.util.ArrayList; 3 import java.util.Collections; 4 public class Solution { 5 public ArrayList<String> Permutation(String str) { 6 List<String> result = new ArrayList<String>(); 7 if(str.length()==0) return (ArrayList)result; 8 function(str.toCharArray(),result,0); 9 Collections.sort(result); 10 return (ArrayList)result; 11 } 12 public void function(char [] chr,List<String> temp,int i){ 13 if(i==chr.length-1){ 14 if(!temp.contains(new String(chr))){ 15 temp.add(new String(chr)); 16 return; 17 } 18 }else{ 19 for(int j=i;j<chr.length;j++){ 20 swap(chr,i,j); 21 function(chr,temp,i+1); 22 swap(chr,i,j); 23 } 24 } 25 } 26 public void swap(char[] chr,int i,int j){ 27 if(i!=j){ 28 char m = chr[i]; 29 chr[i]= chr[j]; 30 chr[j]= m; 31 } 32 } 33 }
这道题确实好难理解啊,来自与牛客上的解答图片可以帮助自己理解
原文：https://www.cnblogs.com/shareidea94/p/10894618.html