题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

  对题目的理解，就是一个全排列。我们可以使用暴力法对其求解。比如题目给的样例是abc，那么就有如下暴力结果： [ aaa、aab、aac ] 、[ aba、abb、abc] 、[ aca、acb、acc] 、[ baa、bab、bac] 、[ bba、bbb、bbc] 、[ bca、bcb、bcc] 、[ caa、cab、cac] 、[ cba、cbb、cbc] 、[ cca、ccb、ccc]   这九大类。如果想要优化则可以适当剪枝，添加判断语句，在合理的位置跳出循环。   本题，我使用了暴力求解，在求解之前，我首先对str排序，这样循环下去就是按照上方书写的顺序进行。终结条件就是子字符串等于字符串或者大于字符串。由于字符串是引用，这一条路走不通记得要返回走下一条路的时候，要对子字符串还原操作。

AC代码

import java.util.ArrayList; import java.util.Arrays; public class Solution { ArrayList<String> list = new ArrayList<String>(); public ArrayList<String> Permutation(String str) { if(str.length() == 0) return list; f(str,""); return list; } public void f(String str, String s) { if (s.length() == str.length()) { char[] c1 = s.toCharArray(); Arrays.sort(c1); char[] c2 = str.toCharArray(); Arrays.sort(c2); String s1 = new String(c1); String s2 = new String(c2); if (s1.equals(s2)){ if(!list.contains(s)) list.add(s); } else { return; } } if(s.length() > str.length()) return ; for (int i = 0; i < str.length(); i++) { String t = s; s = s + str.charAt(i); f(str, s); s = t; } } }