输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
解题思路:把字符串解析成一个char数组,然后设置一个和char对应的boolean数组,使用boolean中的值来控制对应char数组的值是否可以使用。去重的时候使用arraylist中的contains来判断数组中是否包含相同的数据,如果包含就不添加。
public ArrayList<String> Permutation(String str) { ArrayList<String> result = new ArrayList<>(); if(str.length() == 0){ return result; } //进行标志的数组 Boolean[] booleans = new Boolean[str.length()]; for (int i = 0; i < booleans.length; i++) { booleans[i] = true; } char[] chars = str.toCharArray(); search(chars,booleans,result,""); return result; } public void search(char[] chars, Boolean[] booleans,ArrayList<String> result,String str){ if(str.length() == chars.length){ //最后添加的时候看看是否存在重复的,如果存在就不添加了 if(!result.contains(str)){ result.add(str); } } for (int i = 0; i < chars.length; i++) { //判断当前数据是否可以使用 if(booleans[i]){ booleans[i] = false; search(chars,booleans,result,str+chars[i]); booleans[i] = true; }else{ continue; } } }