题目描述
输入一个字符串,按照字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
分析：全排列问题属于典型的递归问题，对于递归问题，我们首先要做的是找到递归函数的出口，即递归终止条件，找出f(n)和f(n-1)之间的关系，我们f(n)为将第n个字符插入到n-1个字符的任何一个排列的任意一个位置上。求出所有权排列后再对其进行字典排序。
代码如下所示：
1 import java.util.ArrayList;
2 public class Solution {
3 public ArrayList<String>
Permutation(String str) {
4 return findPermutationStr(str);
5
6 }
7 private static ArrayList<String>
findPermutationStr(Stringstr) {
8 ArrayList<String> strList=
findPermutations(str);
9 ArrayList<String> strList2 =
new ArrayList<String>
();
10 for (
int i = 0; i < strList.size(); i++
) {
11 if (!
strList2.contains(strList.get(i))) {
12 strList2.add(strList.get(i));
13 }
14
15 }
16 String tmpString =
null;
17 // [aabc, abac, abca, aacb, acab, acba, baac, baca, bcaa, caab, caba,
18 // cbaa]
19 for (
int i = 0; i < strList2.size(); i++
) {
20 for (
int j = 0; j < strList2.size() - 1 - i; j++
) {
21 if (compareStr(strList2.get(j), strList2.get(j+1)) >0
) {
22 tmpString =
strList2.get(j);
23 strList2.set(j, strList2.get(j + 1
));
24 strList2.set(j + 1
, tmpString);
25 }
26 }
27 }
28 return strList2;
29 }
30 private static ArrayList<String>
findPermutations(String str) {
31 ArrayList<String> strList =
new ArrayList<String>
();
32 if (str.length() == 0
) {
33 return strList;
34 }
35 if (str.length() == 1
) {
36 strList.add(str);
37 return strList;
38 }
39 if (str.length() == 2
) {
40 char[] chArry =
str.toCharArray();
41 strList.add(str);
42 if (chArry[0] != chArry[1
]) {
43 String s =
new String(
new char[] { chArry[1], chArry[0
] });
44 strList.add(s);
45 }
46
47 return strList;
48 }
49
50 ArrayList<String> subStrPermutation敏感词indPermutations(str.substring(1
));
51 char firstChar = str.charAt(0
);
52 for (String s : subStrPermutations) {
53 String tmpStr = firstChar +
s;
54 strList.add(tmpStr);
55 char[] charArry =
tmpStr.toCharArray();
56 for (
int i = 0; i < tmpStr.length() - 1; i++
) {
57 char t =
charArry[i];
58 charArry[i] = charArry[i + 1
];
59 charArry[i + 1] =
t;
60 strList.add(
new String(charArry));
61 }
62 }
63 return strList;
64 }
65
66 static int compareStr(String str1, String str2) {
67 if (str1.length() !=
str2.length()) {
68 return str1.length() > str2.length() ? 1 : -1
;
69 }
70 for (
int i = 0; i < str1.length(); i++
) {
71 if (str1.charAt(i) ==
str2.charAt(i)) {
72 continue;
73 }
74 return str1.charAt(i) > str2.charAt(i)?1:-1
;
75
76 }
77 return 0
;
78 }
79 }
转载于:https://www.cnblogs.com/huntertoung/p/4803180.html
